P4427 [BJOI2018]求和

题面: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;
}

P4427 [BJOI2018]求和

原文：https://www.cnblogs.com/ukcxrtjr/p/11673256.html