返回题解分享
讨论 / 题解分享/ 帖子详情

战争 - 题解

#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;
}
0 回复 0 转发 0 喜欢 2 阅读
回复 (0)
默认 最新
暂无回复,快来抢沙发!