[BJOI2018]求和

link

其实可以用$sum(i,j)$表示从$i$到$1$的$k$次方的值，然后就是$lca$的基本操作

注意，能一起干的事情就一起搞，要不会超时

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#define int long long

#define mod 998244353

using namespace std;

const int N=;

inline int read(){

    int f=,ans=;char c=getchar();

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){ans=ans*+c-'';c=getchar();}

    return f*ans;

}

struct node{

    signed u,v,nex;

}x[N<<];

signed n,m,cnt;

int sum[N][];

signed head[N],deep[N],fa[N][];

void add(signed u,signed v){

    x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;

}

int ksm(int a,int b){

    if(a==) return ;

    int ans=;

    a%=mod;

    while(b){

        if(b&) ans*=a,ans%=mod;

        a*=a,a%=mod;

        b>>=;

    }return ans;

}

void dfs(signed f,signed fath){

    deep[f]=deep[fath]+,fa[f][]=fath;

    for(signed i=;i<=;i++) sum[f][i]=sum[fath][i]+ksm(deep[f],i);

    for(signed i=;(<<i)<=deep[f];++i) fa[f][i]=fa[fa[f][i-]][i-];

    for(signed i=head[f];i!=-;i=x[i].nex){

        if(x[i].v==fath) continue;

        dfs(x[i].v,f);

    }

}

int Log2[N];

signed lca(signed u,signed v){

    if(deep[u]<deep[v]) swap(u,v);

    for(signed i=Log2[u];i>=;--i)

        if(deep[u]-(<<i)>=deep[v]) u=fa[u][i];

    if(u==v) return u;

    for(signed i=Log2[v];i>=;--i){

        if(fa[u][i]==fa[v][i]) continue;

        u=fa[u][i],v=fa[v][i];

    }return fa[u][];

}

signed q;

bool ff;

signed main(){

    memset(head,-,sizeof(head));

    n=read();

    for(signed i=;i<n;++i){

        int u=read(),v=read();

        add(u,v),add(v,u);

    }deep[]=-;Log2[]=;

    for(int i=;i<=n;++i) Log2[i]=Log2[i>>]+;

    dfs(,);

    q=read();

    while(q--){

        int u=read(),v=read(),k=read();

        int ls=lca(u,v);

        printf("%d\n",(((sum[u][k]+sum[v][k]-*sum[ls][k]+ksm(deep[ls],k))%mod+mod)%mod));

    }

    return ;

}