题意：给出一棵树，求出M条$u->v$的路径上 每个点与根节点的距离的K次方和
思路：感谢lhy大佬提供的思路
设点x到根的路径上的点的K次方和为$sum_x$
我们可以推得一个式子：路径上的点的$K$次方和=$sum_{u}$+$sum_{v}$-$sum_{LCA_{uv}}*2$+LCA本身的$K$次方和
实际上还可以优化成：路径上的点的$K$次方和=$sum_{u}$+$sum_{v}$-$sum_{LCA_{uv}}$-$sum_{fa[lca_{uv}]}$
所以，我们要做的就是：
求出每个点到根的链上的点的$K$次方和 + 倍增求LCA。至此问题迎刃而解
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 const long long mod=998244353; 4 unsigned long long cc,to[600100],net[600100],fr[300100],dep[300100]; 5 unsigned long long f[300100][51],fa[300100][20]; 6 void addedge(unsigned long long u,unsigned long long v) 7 { 8 cc++; 9 to[cc]=v;net[cc]=fr[u];fr[u]=cc; 10 } 11 void dfs( long long x) 12 { 13 unsigned long long tmp=1; 14 for ( long long i=1;i<=50;i++) 15 { 16 tmp=(tmp*dep[x])%mod; 17 f[x][i]=(f[fa[x][0]][i]+tmp); 18 if(f[x][i]>=mod) f[x][i]-=mod; 19 }//暴力求sum[x] 20 for ( long long i=1;i<=19;i++) 21 fa[x][i]=fa[fa[x][i-1]][i-1];//LCA 22 for ( long long i=fr[x];i;i=net[i]) 23 { 24 if (to[i]==fa[x][0]) continue; 25 fa[to[i]][0]=x;dep[to[i]]=dep[x]+1;dfs(to[i]); 26 } 27 } 28 unsigned long long findLca(unsigned long long u,unsigned long long v) 29 { 30 if (dep[u]>dep[v]) swap(u,v); 31 for ( long long i=19;i>=0;i--) 32 { 33 if (dep[fa[v][i]]>=dep[u]) v=fa[v][i]; 34 } 35 if (u==v) return u; 36 for ( long long i=19;i>=0;i--) 37 if (fa[u][i]!=fa[v][i]) 38 { 39 u=fa[u][i];v=fa[v][i]; 40 } 41 return fa[u][0]; 42 } 43 int main() 44 { 45 unsigned long long n,u,v,m,k; 46 cin>>n; 47 for (unsigned long long i=1;i<n;i++) 48 { 49 scanf("%lld%lld",&u,&v); 50 addedge(u,v);addedge(v,u);//树是无向边 51 } 52 dfs(1); 53 cin>>m; 54 for (unsigned long long i=1;i<=m;i++) 55 { 56 scanf("%lld%lld%lld",&u,&v,&k); 57 int fafa=findLca(u,v); 58 printf("%lld ",(((f[u][k]+f[v][k])%mod-f[fafa][k]+mod)%mod-f[fa[fafa][0]][k]+mod)%mod); 59 } 60 return 0; 61 }
反思：膜的时候要注意不能爆负数,否则你会挂得很惨