题目：洛谷P4427。

题目大意：

一棵树，根节点1深度为0。设点i的深度为\(d_i\)。

现在有m个询问，每个询问选择2个点x,y,并给出k。问x到y路径上\(\sum d_i ^k\)。

解题思路：

由于k最大50，我们预处理出k等于1~50的所有节点的树上差分，然后LCA即可。

C++ Code：

#include
     
      #define N 300005#define md 998244353#define LoveLive long longint n,head[N],cnt=0,k;LoveLive dep[51][N],s[51][N];int p[N][22];inline int readint(){	int c=getchar(),d=0;	for(;!isdigit(c);c=getchar());	for(;isdigit(c);c=getchar())	d=(d<<3)+(d<<1)+(c^'0');	return d;}struct edge{	int to,nxt;}e[N<<1];void dfs(int now){	for(int i=head[now];i;i=e[i].nxt)	if(!~dep[1][e[i].to]){		p[e[i].to][0]=now;		dep[1][e[i].to]=dep[1][now]+1;		dfs(e[i].to);	}}void ssum(int now){	for(int i=head[now];i;i=e[i].nxt)	if(dep[1][e[i].to]==dep[1][now]+1){		s[k][e[i].to]=(s[k][now]+dep[k][e[i].to])%md;		ssum(e[i].to);	}}int lca(int x,int y){	if(dep[1][x]
      
       =0;--i)	if(dep[1][p[x][i]]>=dep[1][y])x=p[x][i];	if(x==y)return x;	for(int i=21;i>=0;--i)	if(p[x][i]&&p[x][i]!=p[y][i])x=p[x][i],y=p[y][i];	return p[x][0];}int main(){	n=readint();	memset(head,0,sizeof head);	for(int i=1;i