[BZOJ5293][BJOI2018]求和(倍增)

裸的树上倍增。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define rep(i,l,r) for (int i=(l); i<=(r); i++)

 using namespace std;

 const int N=,mod=;

 struct E{ int to,nxt; }e[N*];

 int fa[N],a[N],dep[N],f[N][],sm[N][],pow[N][];

 int h[N],cnt,n,m,x,y,k;

 void add(int u,int v){ e[++cnt].to=v; e[cnt].nxt=h[u]; h[u]=cnt; }

 void Build(int x){

     dep[x]=dep[fa[x]]+;

     sm[x][]=; pow[x][]=;

     rep(i,,){

         pow[x][i]=((long long)pow[x][i-]*(long long)dep[x])%mod;

         sm[x][i]=(sm[fa[x]][i]+pow[x][i])%mod;

     }

     for (int i=h[x]; i; i=e[i].nxt)

         if (e[i].to!=fa[x]){

             fa[e[i].to]=x;

             f[e[i].to][]=x;

             Build(e[i].to);

         }

 }

 int LCA(int x,int y){

     if (dep[x]<dep[y]) swap(x,y);

     for (int i=; i>=; --i)

         if (dep[f[x][i]]>=dep[y]) x=f[x][i];

     if (x==y) return x;

     for (int i=; i>=; --i)

         if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];

     return fa[x];

 }

 int main(){

     freopen("sum.in","r",stdin);

     freopen("sum.out","w",stdout);

     scanf("%d",&n);

     rep(i,,n-) scanf("%d%d",&x,&y),add(x,y),add(y,x);

     dep[]=-; Build();

     rep(i,,) rep(j,,n) f[j][i]=f[f[j][i-]][i-];

     scanf("%d",&m);

     rep(i,,m){

         scanf("%d%d%d",&x,&y,&k); int lca=LCA(x,y);

         printf("%d\n",((sm[x][k]+sm[y][k]-sm[fa[lca]][k]-sm[lca][k])%mod+mod)%mod);

     }

     return ;

 }