P4427 [BJOI2018]求和
懒得写了（雾
#include<bits/stdc++.h>
#define il inline
#define vd void
typedef long long ll;
il int gi(){
int x=0,f=1;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-')f=-1;
ch=getchar();
}
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
return x*f;
}
#define mod 998244353
int fir[300010],dis[600010],nxt[600010],id,dep[300010];
int st[19][300010];
il vd link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
ll C[101][101],B[51][101],inv[101];
il ll pow(ll x,ll y){
ll ret=1;
while(y){
if(y&1)ret=ret*x%mod;
x=x*x%mod;y>>=1;
}
return ret;
}
il ll calc(ll k,ll n){
if(n<0)return 0;
ll ret=0;
for(int i=1;i<=k+1;++i)ret+=C[k+1][i]*B[k][k+1-i]%mod*pow((n+1)%mod,i)%mod;
return ret%mod*inv[k+1]%mod;
}
il vd dfs(int x,int fa=-1){
for(int i=fir[x];i;i=nxt[i]){
if(dis[i]==fa)continue;
dep[dis[i]]=dep[x]+1;
st[0][dis[i]]=x;
dfs(dis[i],x);
}
}
il int LCA(int a,int b){
if(dep[a]<dep[b])std::swap(a,b);
int c=dep[a]-dep[b];
for(int i=18;~i;--i)if(c&(1<<i))a=st[i][a];
for(int i=18;~i;--i)if(st[i][a]^st[i][b])a=st[i][a],b=st[i][b];
if(a^b)a=st[0][a];
return a;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("4427.in","r",stdin);
freopen("4427.out","w",stdout);
#endif
int n=gi(),a,b;
for(int i=1;i<n;++i)a=gi(),b=gi(),link(a,b),link(b,a);
dfs(1);
C[0][0]=1;
for(int i=1;i<101;++i){
C[i][0]=1;
for(int j=1;j<=i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
}
inv[1]=1;for(int i=2;i<101;++i)inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
for(int k=1;k<51;++k){
B[k][0]=1;
for(int i=1;i<101;++i){
for(int j=0;j<i;++j)B[k][i]+=C[i+1][j]*B[k][j]%mod;
B[k][i]=(mod-B[k][i]%mod*inv[i+1]%mod)%mod;
}
}
for(int i=1;i<19;++i)
for(int j=1;j<=n;++j)
st[i][j]=st[i-1][st[i-1][j]];
int m=gi(),c,k;
while(m--){
b=gi(),c=gi(),a=LCA(b,c),k=gi();
printf("%lld\n",(calc(k,dep[b])+calc(k,dep[c])-calc(k,dep[a])-calc(k,dep[a]-1)+mod+mod)%mod);
}
return 0;
}