rt,只 AC 了 hack 的最后一个点

#include <bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+(ch^48);
	return f*x;
}
const int mod=998244353;
int n,m,u,v,w,dep[300005],fa[300005],dfn[300005],cnt,mn[300005][20],p[300005][55];
vector<int> g[300005];
void dfs(int x,int fat){
	fa[x]=fat,dfn[x]=++cnt,mn[cnt][0]=x;
	for(int i=0;i<g[x].size();i++)
		if(g[x][i]^fat)
			dep[g[x][i]]=dep[x]+1,dfs(g[x][i],x);
}
inline int gmin(int l,int r){
	if(dfn[l]>dfn[r]) swap(l,r);
    l=dfn[l]+1,r=dfn[r];
	int t=log2(r-l+1),res=mn[l][t];
    if(dfn[mn[r-(1<<t)+1][t]]<dfn[res]) res=mn[r-(1<<t)+1][t];
    return res;
}
int main(){
	n=read();
	for(int i=1;i<n;i++)
		u=read(),v=read(),g[u].push_back(v),g[v].push_back(u);
	for(int i=1;i<=n;i++){
		p[i][1]=i;
		for(int j=2;j<=50;j++)
			p[i][j]=1ll*p[i][j-1]*i%mod;
	}
    // printf("%d\n",p[3][3]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=50;j++)
			p[i][j]=(p[i-1][j]+p[i][j])%mod;
    // printf("%d\n",p[3][2]);
	dfs(1,0);	
	for(int j=1;(1<<j)<=n;j++)
		for(int i=1;i+(1<<j)<=n+1;i++)
            if(dfn[mn[i][j-1]]<dfn[mn[i+(1<<j-1)][j-1]]) mn[i][j]=mn[i][j-1];
            else mn[i][j]=mn[i+(1<<j-1)][j-1];
	m=read();
    // for(int i=1;i<=n;i++)
        // printf("%d\n",dfn[i]);
	while(m--){
		u=read(),v=read(),w=read();
		int lca=(u^v?fa[gmin(u,v)]:u);
		printf("%d\n",((p[dep[u]][w]+p[dep[v]][w]-p[dep[lca]][w]-p[max(dep[lca]-1,0)][w])%mod+mod)%mod);
	}
	return 0;
}