rt样例输出276 640187589

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+5,mod=998244353;
int n,m,cnt,idx;
int head[N],dep[N],fa[N],son[N],siz[N],top[N],id[N],a[N];
ll f[N][51];
struct edge
{
	int next,to;
}e[N<<1];
struct segment_tree
{
	int l,r,val[51];
}t[N<<2];

void add_edge(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;
}

void push_up(int x)
{
	for(int i=0;i<=50;i++)
	  t[x].val[i]=(t[x<<1].val[i]+t[x<<1|1].val[i])%mod;
}

void build(int l,int r,int x)
{
	t[x].l=l;
	t[x].r=r;
	if(l==r)
	{
		for(int i=0;i<=50;i++)
		  t[x].val[i]=f[dep[a[l]]][i];
		return;
	}
	int mid=l+r>>1;
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	push_up(x);
}

int query(int nl,int nr,int k,int l,int r,int x)
{
	if(nl<=l&&r<=nr)
	{
		return t[x].val[k];
	}
	int mid=l+r>>1,res=0;
	if(nl<=mid) res+=query(nl,nr,k,l,mid,x<<1)%mod;
	if(nr>mid) res+=query(nl,nr,k,mid+1,r,x<<1|1)%mod;
	return res%mod;
}

void dfs1(int u,int fath)
{
	dep[u]=dep[fath]+1;
	fa[u]=fath;
	siz[u]=1;
	for(int i=head[u];i;i=e[i].next)
	{
		int v=e[i].to;
		if(v==fath) continue;
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[son[u]])
		  son[u]=v;
	}
}

void dfs2(int u,int fst)
{
	id[u]=++idx;
	a[idx]=u;
	top[u]=fst;
	if(!son[u]) return;
    dfs2(son[u],fst);
    for(int i=head[u];i;i=e[i].next)
    {
    	int v=e[i].to;
    	if(v==fa[u]||v==son[u]) continue;
    	dfs2(v,v);
	}
}

int trlist_query(int u,int v,int k)
{
	int res=0;
	while(top[u]!=top[v])
	{
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		res+=query(id[top[u]],id[u],k,1,n,1);
		res%=mod;
		u=fa[top[u]];
	}
	if(dep[u]>dep[v]) swap(u,v);
	res+=query(id[u],id[v],k,1,n,1);
	res%=mod;
	return res;
}

void pow_init()
{
	for(int i=1;i<=N;i++)
	  f[i][0]=1;
	for(int i=1;i<=N;i++)
	  for(int j=1;j<=50;j++)
	    f[i][j]=(f[i][j-1]*i)%mod;
}

signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int u,v;
		cin>>u>>v;
		add_edge(u,v);
		add_edge(v,u);
	}
	dfs1(1,0);
	dfs2(1,1);
	pow_init();
	build(1,n,1);
	cin>>m;
	while(m--)
	{
		int u,v,k;
		cin>>u>>v>>k;
		cout<<trlist_query(u,v,k)<<'\n';
	}
	return 0;
}