这是一道树链剖分/树上差分/LCA的题目……

本来想打一遍树剖，但是被那强大的码量劝退了，于是我开始思考树上差分。

我们先把每个点深度的k次方打一个表，之后我们因为要做减法，所以我们令val_i,k​表示i到1号点路径上点深度的k次方之和

然后问题来了，我们维护的是点权和，所以我们发现直接减的话会导致lca这个点没算，所以略微改一下公式，使lca这个点也被算一次

然后我们询问u,v,k的时候输出val_u,k​+val_v,k​−val_lca(u,v)​−val_{falca(u,v)​​}即可

问题就是如何找lca了，这个用倍增预处理，在倍增寻找即可。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 typedef long long ll; 7 inline int read() { 8     int ret=0; 9     int op=1;10     char c=getchar();11     while(c<'0'||c>'9') {
    if(c=='-') op=-1; c=getchar();}12     while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();13     return ret*op;14 }15 const ll mod=998244353;16 struct node {17     int next,to;18 }a[300010<<1];19 int num,head[300010<<1];20 int n,m;21 int f[300010][25];22 ll d[300010];23 ll pow[60],val[300010][60];24 inline void add(int from,int to) {25     a[++num].next=head[from]; a[num].to=to;    head[from]=num;26     swap(from,to);27     a[++num].next=head[from]; a[num].to=to;    head[from]=num;28 }29 void dfs(int u,int fa) {30     for(int i=0;f[u][i];i++) f[u][i+1]=f[f[u][i]][i];31     for(int i=head[u];i;i=a[i].next) {32         int v=a[i].to;33         if(v==fa) continue ;34         f[v][0]=u;35         d[v]=d[u]+1;36         for(int j=1;j<=50;j++) pow[j]=pow[j-1]*d[v]%mod;37         for(int j=1;j<=50;j++) val[v][j]=(val[u][j]+pow[j])%mod;38         dfs(v,u);39     }40 }41 int lca(int x,int y) {42     if(d[x]
          
           =0;i--)44         if(d[f[x][i]]>=d[y]) x=f[x][i];45     if(x==y) return x;46     for(int i=20;i>=0;i--)47         if(f[x][i]!=f[y][i]) {48             x=f[x][i];49             y=f[y][i];50         }51     return f[x][0];52 }53 int main() {54     n=read();55     for(int i=1;i