1 条题解

  • 0
    @ 2025-1-13 22:08:29
    #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
    上传者