link
记 d u d_u du 表示 u u u 到 1 1 1 的距离。
预处理出 s u m u = ∑ v ∈ T u 2 d v − d u sum_u=\sum\limits_{v\in T_{u}}2^{d_v-d_u} sumu=v∈Tu∑2dv−du。
考虑两种情况
- x x x 和 y y y 都不是 l c a lca lca。答案就是 2 dis ( x , y ) ∑ u ∈ T x 2 d u − d x ∑ v ∈ T y 2 d v − d y 2^{\operatorname{dis}(x,y)}\sum\limits_{u\in T_x}2^{d_u-d_x}\sum\limits_{v\in T_y}2^{d_v-d_y} 2dis(x,y)u∈Tx∑2du−dxv∈Ty∑2dv−dy,直接用 s u m sum sum 求即可。
- 否则,就要进行换根的操作,令 x x x 为深度小的那个点,我们想要求以 x x x 的儿子(往下走可以走到 y y y)为根的 s u m sum sum。简单维护即可。具体可以参照代码。
由于要求 l c a lca lca,我采用树剖的方法,其实可以用 tarjan,我不会。
这里要卡常。文章来源:https://www.toymoban.com/news/detail-740118.html
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)。文章来源地址https://www.toymoban.com/news/detail-740118.html
#include<bits/stdc++.h>
using namespace std;
constexpr int N=1e6+1;
constexpr long long mod=998244353ll;
int n,q;
int head[N],nxt[N<<1],to[N<<1],cnt;
int dep[N],sz[N],fa[N],top[N],son[N];
int sum[N],pw[N],sum1[N];
void add(int u,int v)
{
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
inline int MOD(int x){return x>=mod?x-mod:x;}
void dfs1(int u,int F)
{
dep[u]=dep[F]+1;
fa[u]=F;
sz[u]=1;
for(int i=head[u];i;i=nxt[i]){
if(to[i]!=F){
dfs1(to[i],u);
sz[u]+=sz[to[i]];
if(sz[son[u]]<sz[to[i]]) son[u]=to[i];
sum[u]=MOD(sum[u]+sum[to[i]]);
}
}
sum[u]=MOD((sum[u]<<1)+1);
}
void dfs2(int u,int t)
{
top[u]=t;
if(son[u]) dfs2(son[u],t);
for(int i=head[u];i;i=nxt[i]){
if(to[i]!=fa[u]&&to[i]!=son[u]){
dfs2(to[i],to[i]);
}
}
}
int lca(int u,int v)
{
while(top[u]!=top[v]){
if(dep[top[u]]<dep[top[v]]) swap(u,v);
u=fa[top[u]];
}
return dep[u]>dep[v]?v:u;
}
void dfs3(int u)
{
int x=0;
for(int i=head[u];i;i=nxt[i]) if(to[i]!=fa[u]) x=MOD(x+sum[to[i]]);
for(int i=head[u];i;i=nxt[i]){
if(to[i]!=fa[u]){
sum1[to[i]]=MOD((MOD(MOD(x+sum1[u])+mod-sum[to[i]])<<1)+1);
dfs3(to[i]);
}
}
}
int main()
{
freopen("d.in","r",stdin);
freopen("d.out","w",stdout);
cin.tie(0)->sync_with_stdio(0);
cin>>n;
for(int i=1,x,y;i<n;i++){
cin>>x>>y;
add(x,y),add(y,x);
}
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=MOD(pw[i-1]<<1);
dfs1(1,0);
dfs2(1,1);
dfs3(1);
cin>>q;
for(int i=1,x,y;i<=q;i++){
cin>>x>>y;
int Lca=lca(x,y);
if(x!=Lca&&y!=Lca) cout<<1ll*sum[x]*sum[y]%mod*pw[dep[x]+dep[y]-2*dep[Lca]]%mod<<"\n";
else{
if(dep[x]>dep[y]) swap(x,y);
int xx=dep[y]-dep[x]-1,now=y;
if(xx>0){
while(top[x]!=top[now]){
now=top[now];
if(fa[now]==x) goto a;
now=fa[now];
}
now=son[x];
}
a:cout<<1ll*sum[y]*sum1[now]%mod*pw[dep[x]+dep[y]-2*dep[Lca]]%mod<<"\n";
}
}
}
到了这里,关于NOIP2023模拟9联测30-金牌的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!