已全开longlong，没有输出负数

树剖板子和过来的错不了应该，但是预处理也不像会炸的样子。。。

我很 很 很迷惑。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=300010,mod=998244353;
LL n,m,cnt,tot;
LL hd[N],to[N<<1],nxt[N<<1];
LL fa[N],dep[N],top[N],sz[N],son[N],id[N],cur[N];
LL sum[N][55];
void add(LL u,LL v){
    to[++cnt]=v;
    nxt[cnt]=hd[u];
    hd[u]=cnt;
}
void dfs1(LL u,LL fat){
    sz[u]=1;dep[u]=dep[fat]+1;fa[u]=fat;
    for(LL i=hd[u];i;i=nxt[i]){
        LL v=to[i],maxx=0;
        if(v==fat) continue;
        dfs1(v,u);sz[u]+=sz[v];
        if(sz[v]>maxx) maxx=sz[v],son[u]=v;
    }
    return;
}
void dfs2(LL u,LL topf){
    id[u]=++tot,cur[tot]=dep[u];top[u]=topf;
    if(!son[u]) return;
    dfs2(son[u],topf);
    for(LL i=hd[u];i;i=nxt[i]){
        LL v=to[i];
        if(fa[u]==v||v==son[u]) continue;
        dfs2(v,v); 
    }
    return;
}//板子
void init(){
    for(LL i=1;i<=n;i++){
        LL s=1;
        for(LL j=0;j<=50;j++){
            sum[j][i]=((sum[j][i-1]+s)%mod+mod)%mod;
            s=(s*cur[i]%mod+mod)%mod;
        }
    }
    return;
}//预处理
LL query(LL rt,LL l,LL r,LL L,LL R,LL k){
    return ((sum[k][R]-sum[k][L-1])%mod+mod)%mod;
}
LL qrange(LL x,LL y,LL k){
    LL ret=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]]) swap(x,y);
        ret=(ret+query(1,1,n,id[top[x]],id[x],k))%mod;
        x=fa[top[x]];
    }
    if(dep[x]>dep[y]) swap(x,y);
    if(id[x]==id[y]) return ret;
    ret=(ret+query(1,1,n,id[x],id[y],k))%mod;
    return (ret+mod)%mod;
}//板子
int main(){
    scanf("%lld",&n);
    for(LL i=1,u,v;i<n;i++){
        scanf("%lld%lld",&u,&v);
        add(u,v);add(v,u);
    }
    dep[0]=-1;
    dfs1(1,0);dfs2(1,1);
    init();scanf("%lld",&m);
    for(LL i=1,x,y,k;i<=m;i++){//cout<<"*"<<endl;
        scanf("%lld%lld%lld",&x,&y,&k);
        printf("%lld\n",qrange(x,y,k));
    }
    return 0;
}