求和VII

宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

master对树上的求和非常感兴趣。他生成了一棵有根树，并且希望多次询问这棵树上一段路径上所有节点深度的k次方和，而且每次的k可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了pupil，但pupil并不会这么复杂的操作，你能帮他解决吗

输入

第一行包含一个正整数n，表示树的节点数。
之后n−1行每行两个空格隔开的正整数i,j，表示树上的一条连接点i和点j的边。
之后一行一个正整数m，表示询问的数量。
之后每行三个空格隔开的正整数i,j,k，表示询问从点i到点j的路径上所有节点深度的k次方和。由于这个结果可能非常大，输出其对998244353取模的结果。
树的节点从1开始标号，其中1号节点为树的根。

输出

对于每组数据输出一行一个正整数表示取模后的结果。

样例输入

样例输出

33
503245989

提示

以下用di)表示第i个节点的深度。
对于样例中的树，有d1)=0,d2)=1,d3)=1,d4)=2,d5)=2。
因此第一个询问答案为25+15+05) mod 998244353=33，第二个询问答案为245+145+245) mod 998244353=503245989。

对于30%的数据，1≤n,m≤100；
对于60%的数据，1≤n,m≤1000；
对于100%的数据，1≤n,m≤300000,1≤k≤50。

挺有有意思的这个题

开始也是看了大佬们的博客，一脸懵逼，最后自己想了个通俗易懂的办法；顺利AC；

大意是给你一棵树，又多次询问，每次给定两个端点，问这两个端点及其路径所经过的点的深度的平方和；

1.BFS 求深度

2.因为k<=50，所以根据深度预处理i次方i>=1&&i<=50)

3,感觉大家卡住的点是在求路径上；这个的解决关键在于“找爸爸”；既每个点找出他的根节点（紧连着他的上一个节点）（BFS过程中一起处理了），然后每次给你两个点，看他们的深度，深度不同把深度大的k次方的加到ans里面，然后把他的父亲拿出来递归，如果递归到两个数深度一样，但是父亲不同也是要继续，只有当两者相等时才结束；

4.。。差不多就这些，下面是代码；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 300001
#define mod 998244353
vector<int>a[300001];
int fa[300001];
ll sum[maxn][55];
queue<int>rec;
int b[maxn],n,k,s;
void init)//预处理每个点的1-50次方
{
forint i=1; i<=n; i++)
    {
        forint j=1; j<=50; j++)
        {
            ifj==1)
            {sum[i][j]=b[i];}
            else
            {sum[i][j]=sum[i][j-1]*b[i]%mod;}
        }
    }
}
void diguiint r,int t)//关键部分，递归求路径所有点的k次方
{
    ifb[r]<b[t])
    {
        s=s+sum[t][k])%mod;
        diguir,fa[t]);
    }
    else ifb[r]>b[t])
    {
        s=s+sum[r][k])%mod;
        diguifa[r],t);
    }
    else ifb[r]==b[t]&&fa[r]==fa[t]&&r!=t)
    {
        s=s+sum[r][k])%mod;
        s=s+sum[t][k])%mod;
        s=s+sum[fa[r]][k])%mod;
        return ;
    }
    else ifr==t)
    {
        s=s+sum[r][k])%mod;
        return ;
    }
    else ifb[r]==b[t]&&fa[r]!=fa[t])
    {
        s=s+sum[r][k])%mod;
        s=s+sum[t][k])%mod;
        diguifa[r],fa[t]);
    }
}
inline int read)//读入挂，输入有点多
{
    int x = 0,f = 1;
    char c = getchar);
    while c < '0' || c > '9') && c != EOF)
    {
        if c == '-') f = -1;
        c = getchar);
    }
    while c <='9' && c >='0') && c != EOF)
    {
        x = x * 10 + c - '0';
        c = getchar);
    }
    return x * f;
}
void bfsint x)//BFS求深度
{
    forint i=0; i<a[x].size); i++)
    {
        ifb[a[x][i]]==0&&a[x][i]!=1)
        {
            fa[a[x][i]]=x;//顺便记录一下父节点
            b[a[x][i]]=b[x]+1;
            rec.pusha[x][i]);
        }

    }
}
int main)
{
    n=read);
    fa[1]=1;//注意
    forint i=1; i<n; i++)//vector建边
    {
        int p,q;
        p=read);
        q=read);
        a[p].push_backq);
        a[q].push_backp);
    }
    rec.push1);
    b[1]=0;//注意
    int cnt=1;
    whilecnt>0)
    {
        int p=rec.front);
        bfsp);
        rec.pop);
        cnt=rec.size);
    }
    init);
    int T;
    T=read);
    int st,en;
    forint i=0; i<T; i++)
    {
        st=read);
        en=read);
        k=read);
        s=0;
        diguist,en);
        printf"%lld
",s);
    }
    return 0;
}