洛谷传送门

BZOJ传送门

---

解析：

连修改都不带还玩什么。。。

直接处理出每个点到根的路径上的所有$K$K次方之和。

然后随便用一个求LCA的方法水过去就行了。

---

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register
#define gc get_char
#define cs const

namespace IO{
	inline char get_char(){
		static cs int Rlen=1<<20|1;
		static char buf[Rlen],*p1,*p2;
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	
	inline int getint(){
		re char c;
		while(!isdigit(c=gc()));re int num=c^48;
		while(isdigit(c=gc()))num=(num+(num<<2)<<1)+(c^48);
		return num;
	}
}
using namespace IO;

cs int mod=998244353;
inline int add(cs int &a,cs int &b){return a+b>=mod?a+b-mod:a+b;}
inline int dec(cs int &a,cs int &b){return a<b?a-b+mod:a-b;}
inline int mul(cs int &a,cs int &b){return (ll)a*b%mod;}
inline int quickpow(int a,int b,int res=1){
	while(b){
		if(b&1)res=mul(res,a);
		a=mul(a,a);
		b>>=1;
	}
	return res;
}

cs int N=3e5+5;
int n,m;
int last[N],nxt[N<<1],to[N<<1],ecnt;
inline void addedge(int u,int v){
	nxt[++ecnt]=last[u],last[u]=ecnt,to[ecnt]=v;
	nxt[++ecnt]=last[v],last[v]=ecnt,to[ecnt]=u;
}

int fa[N],dep[N],top[N],f[N][51];
int siz[N],son[N];

int q[N],qn;
inline void tree_dissection(){
	q[qn=1]=1;
	for(int re i=1,u=1;i<=qn;u=q[++i])
	for(int re e=last[u],v=to[e];e;v=to[e=nxt[e]]){
		if(v^fa[u]){
			fa[v]=u;
			dep[v]=dep[u]+1;
			for(int re i=1,val=dep[v];i<=50;++i,val=mul(val,dep[v]))f[v][i]=add(f[u][i],val);
			q[++qn]=v;
		}
	}
	for(int re i=qn,u=q[qn];i;u=q[--i]){
		siz[fa[u]]+=++siz[u];
		if(siz[u]>siz[son[fa[u]]])son[fa[u]]=u;
	}
	for(int re i=1,u=1;i<=qn;u=q[++i]){
		if(!top[u])top[u]=u;
		if(son[u])top[son[u]]=top[u];
	}
}

inline int LCA(int u,int v){
	while(top[u]^top[v])dep[top[u]]<dep[top[v]]?v=fa[top[v]]:u=fa[top[u]];
	return dep[u]>dep[v]?v:u;
}

signed main(){
	n=getint();
	for(int re i=1;i<n;++i)addedge(getint(),getint());
	tree_dissection();
	m=getint();
	int u,v,k,lca;
	while(m--){
		u=getint(),v=getint(),k=getint();
		lca=LCA(u,v);
		cout<<dec(add(f[u][k],f[v][k]),add(f[lca][k],f[fa[lca]][k]))<<'\n';
	}
	return 0;
}