题面:https://www.luogu.org/problem/P4427
本题设ans[u][i]为1~u的路径上的节点深度的i次方和,这样查询答案时就是ans[u]+ans[v]-ans[lca(u,v)]-ans[fa[lca(u,v)]]
Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<ctime>
#include<set>
using namespace std;
const int N=300005,mod= 998244353;
int n,m,head[N],cnt,anc[N][25],fa[N],dep[N];
long long ans[N][55];
struct Node{
int u,v,nxt;
}edge[N*2];
int ksm(long long a,int b){
long long sum=1;
while(b>0){
if(b&1){
sum=(sum*a)%mod;
}
a=(a*a)%mod;
b/=2;
}
return sum;
}
void add(int u,int v){
++cnt;
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int u){
anc[u][0]=fa[u];
for(int i=1;i<=22;i++){
anc[u][i]=anc[anc[u][i-1]][i-1];
}
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
if(v!=fa[u]){
fa[v]=u;
dep[v]=dep[u]+1;
dfs(v);
}
}
}
int lca(int x,int y){
if(dep[x]<dep[y]){
swap(x,y);
}
for(int i=22;i>=0;i--){
if(dep[anc[x][i]]>=dep[y]){
x=anc[x][i];
}
}
if(x==y){
return x;
}
for(int i=22;i>=0;i--){
if(anc[x][i]!=anc[y][i]){
x=anc[x][i];
y=anc[y][i];
}
}
return anc[x][0];
}
void change(int u){
for(int i=1;i<=50;i++){
ans[u][i]=(ans[fa[u]][i]+ksm(dep[u],i))%mod;
}
for(int i=head[u];i;i=edge[i].nxt){
int v=edge[i].v;
if(v!=fa[u]){
change(v);
}
}
}
long long calc(int x,int y,int k){
int LCA=lca(x,y);
return ((((ans[x][k]+ans[y][k])%mod-ans[LCA][k]+mod)%mod)-ans[fa[LCA]][k]+mod)%mod;
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
dfs(1);
change(1);
scanf("%d",&m);
while(m--){
int s,t,k;
scanf("%d%d%d",&s,&t,&k);
printf("%lld\n",calc(s,t,k));
}
return 0;
}