1 条题解
-
0
#include<bits/stdc++.h> using namespace std; const int N=100005; const long long mod=998244353; long long f[N],g[N],dis[N],ans; vector<int>e[N],r[N]; int fa[N][21],dep[N],n,q,K; void dfs(const int k) { r[k].resize(e[k].size()+2),f[k]=1; for(int i:e[k]) dfs(i),f[k]=f[k]*(f[i]+1)%mod; r[k][e[k].size()]=1; for(int i=e[k].size()-1;i>=0;--i) r[k][i]=r[k][i+1]*(f[e[k][i]]+1)%mod; } void dfs2(const int k) { dis[k]=(dis[fa[k][0]]+f[k])%mod,dep[k]=dep[fa[k][0]]+1; long long s=1; for(int i=0;i<e[k].size();++i) g[e[k][i]]=(g[k]+1)*s%mod*r[k][i+1]%mod,s=s*(f[e[k][i]]+1)%mod,dfs2(e[k][i]); } int LCA(int u,int v) { if(dep[u]<dep[v]) swap(u,v); for(int i=K;i>=0;--i) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i]; if(u==v) return u; for(int i=K;i>=0;--i) if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i]; return fa[u][0]; } int main() { ios::sync_with_stdio(0),cin.tie(0); cin>>n>>q; int u,v,w; for(int i=2;i<=n;++i) cin>>u,e[u].push_back(i),fa[i][0]=u; fa[1][0]=dep[1]=1; dfs(1); dfs2(1); K=__lg(n); for(int i=1;i<=K;++i) for(int j=1;j<=n;++j) fa[j][i]=fa[fa[j][i-1]][i-1]; while(q--) { cin>>u>>v,w=LCA(u,v); ans=dis[u]+dis[v]-2*dis[w]; ans=(ans+(g[w]+1)*f[w])%mod; cout<<(ans+mod)%mod<<'\n'; } return 0; }
- 1
信息
- ID
- 273
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 4
- 已通过
- 1
- 上传者