Rt。评测记录。

#include<bits/stdc++.h>
using namespace std;
#define mod 998244353
struct Edge{int to,next;}edges[114514*3*2]; 
int head[114514*3],tot=0,fa[114514*3][20],lg[114514*3],dep[114514*3],n,m;
bool v[114514*3]={0};
void adde(int from,int to)
{
    edges[tot]={to,head[from]};
    head[from]=tot++;
}
void dfs(int nde,int d) 
{
    v[nde]=1;
    dep[nde]=d;
    if(nde==1) fa[nde][0]=0;  
    for (int i=1;i<=lg[dep[nde]];i++) fa[nde][i]=fa[fa[nde][i-1]][i-1];
    for (int i=head[nde];i!=-1; i=edges[i].next) 
	{
        int nxt=edges[i].to;
        if (!v[nxt]) 
		{
            fa[nxt][0]=nde;
            dfs(nxt,d+1);
        }
    }
}
int lca(int x,int y) 
{
    if (dep[x]<dep[y]) swap(x, y);
    for (int i=lg[dep[x]];i>=0;i--) if (dep[x] - (1<<i) >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i=lg[dep[x]];i>=0;i--) 
        if (fa[x][i] != fa[y][i]) 
		{
            x = fa[x][i];
            y = fa[y][i];
        }
    
    return fa[x][0];
}
int fpow(int a,int n) 
{
    int ans=1;
    a%=mod;
    while(n) 
	{
        if(n&1)ans=1LL*ans*a%mod;
        a=1LL*a*a%mod;
        n>>=1;
    }
    return ans;
}
void pth(int x,int l,vector<int>& nodes) 
{
    while(x != l) nodes.push_back(x),x=fa[x][0];
    nodes.push_back(l);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    lg[0]=-1;
    for (int i=1;i<=200000;i++) lg[i]=lg[i/2]+1;
    memset(head,-1,sizeof(head));
    cin>>n;
    for(int i=1;i<n;i++) 
	{
        int u,v;
        cin>>u>>v;
        adde(u,v),adde(v,u);
    }
    dfs(1,0);
    cin>>m;
    while(m--) 
	{
        int x,y,z;
        cin>>x>>y>>z;
        int l=lca(x,y);
        vector<int>nodes;
        pth(x,l,nodes);
        pth(y,l,nodes);
        if(nodes.size()>1&&nodes.back()==l) nodes.pop_back();
        int sum=0;
        for(int node:nodes) sum=(sum+fpow(dep[node],z))%mod;
        cout<<sum<<endl;
    }
    return 0;
}