LCA+差分【p4427】[BJOI2018]求和

wa了好多次,结果发现括号匹配错了QAQ。

很明显,这题可以预处理出来\(gw[u][i]\)代表从\(1\)到\(u\)路径上点的深度的\(i\)次方的和.(这是一个前缀和.

然后在\(DFS\)的时候预处理出来倍增数组和\(gw\)数组即可.

预处理\(gw\)数组

\[gw[u][i]=gw[fa][i]+ksm(depth[u],i)
\]

然后根据差分

\[gw[x][i]+gw[y][i]-(gw[lca_{x,y}][i]+gw[father[lca_{x,y}]][i])
\]

求出\(x,y\)之间的答案即可.

后面的括号写错了,难受得一逼.QAQ

代码

#include<cstdio>

#include<algorithm>

#include<cctype>

#define mod 998244353

#define int long long

#define N 300008

#define R register

using namespace std;

inline void in(int &x)

{

	int f=1;x=0;char s=getchar();

	while(!isdigit(s)){if(s=='-')f=-1;s=getchar();}

	while(isdigit(s)){x=x*10+s-'0';s=getchar();}

	x*=f;

}

int n,head[N],tot;

struct cod{int u,v;}edge[N<<2];

inline void add(int x,int y)

{

	edge[++tot].u=head[x];

	edge[tot].v=y;

	head[x]=tot;

}

int depth[N],f[N][21],gw[N][53];

int q;

inline int ksm(int x,int y)

{

	R int res=1;

	for(;y;y>>=1,x=x%mod*x%mod)

		if(y&1)res=res%mod*x%mod;

	return res;

}

void dfs(int u,int fa)

{

	f[u][0]=fa;depth[u]=depth[fa]+1;

	for(R int i=1;(1<<i)<=depth[u];i++)

		f[u][i]=f[f[u][i-1]][i-1];

	for(R int i=1;i<=52;i++)

		gw[u][i]=gw[fa][i]+ksm(depth[u],i);

	for(R int i=head[u];i;i=edge[i].u)

	{

		if(edge[i].v==fa)continue;

		dfs(edge[i].v,u);

	}

}

inline int lca(int x,int y)

{

	if(depth[x]>depth[y])swap(x,y);

	for(R int i=20;i>=0;i--)

		if(depth[x]+(1<<i)<=depth[y])

			y=f[y][i];

	if(x==y)return x;

	for(R int i=20;i>=0;i--)

	{

		if(f[x][i]==f[y][i])continue;

		x=f[x][i],y=f[y][i];

	}

	return f[x][0];

}

signed main()

{

	in(n);

	for(R int i=1,x,y;i<n;i++)in(x),in(y),add(x,y);

	depth[1]=-1;dfs(1,1);in(q);

	for(R int i=1,x,y,k;i<=q;i++)

	{

		in(x),in(y),in(k);

		R int la=lca(x,y);

		printf("%lld\n",(((gw[x][k]+gw[y][k])%mod-(gw[la][k]+gw[f[la][0]][k])%mod)+mod)%mod);

	}

}