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

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

#include
      
       #include
       
        #include
        
         #include
         
          #define int long long#define mod 998244353using namespace std;const int N=300001;inline int read(){    int f=1,ans=0;char c=getchar();    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}    return f*ans;}struct node{    signed u,v,nex;}x[N<<1];signed n,m,cnt;int sum[N][51];signed head[N],deep[N],fa[N][20];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==1) return 1;    int ans=1;    a%=mod;    while(b){        if(b&1) ans*=a,ans%=mod;        a*=a,a%=mod;        b>>=1;    }return ans;}void dfs(signed f,signed fath){    deep[f]=deep[fath]+1,fa[f][0]=fath;    for(signed i=1;i<=50;i++) sum[f][i]=sum[fath][i]+ksm(deep[f],i);    for(signed i=1;(1<
          
           <=deep[f];++i) fa[f][i]=fa[fa[f][i-1]][i-1];    for(signed i=head[f];i!=-1;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]
           
            =0;--i) if(deep[u]-(1<
            
             =deep[v]) u=fa[u][i]; if(u==v) return u; for(signed i=Log2[v];i>=0;--i){ if(fa[u][i]==fa[v][i]) continue; u=fa[u][i],v=fa[v][i]; }return fa[u][0];}signed q;bool ff;signed main(){ memset(head,-1,sizeof(head)); n=read(); for(signed i=1;i
             
              >1]+1; dfs(1,0); 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]-2*sum[ls][k]+ksm(deep[ls],k))%mod+mod)%mod)); } return 0;}