问题 K: 求和VII
时间限制: 2 Sec 内存限制: 256 MB
提交: 422 解决: 53
[提交] [状态] [讨论版] [命题人:admin]
题目描述
master对树上的求和非常感兴趣。他生成了一棵有根树，并且希望多次询问这棵树上一段路径上所有节点深度的k次方和，而且每次的k可能是不同的。此处节点深度的定义是这个节点到根的路径上的边数。他把这个问题交给了pupil，但pupil并不会这么复杂的操作，你能帮他解决吗？
输入
第一行包含一个正整数n，表示树的节点数。
之后n−1行每行两个空格隔开的正整数i,j，表示树上的一条连接点i和点j的边。
之后一行一个正整数m，表示询问的数量。
之后每行三个空格隔开的正整数i,j,k，表示询问从点i到点j的路径上所有节点深度的k次方和。由于这个结果可能非常大，输出其对998244353取模的结果。
树的节点从1开始标号，其中1号节点为树的根。
之后n−1行每行两个空格隔开的正整数i,j，表示树上的一条连接点i和点j的边。
之后一行一个正整数m，表示询问的数量。
之后每行三个空格隔开的正整数i,j,k，表示询问从点i到点j的路径上所有节点深度的k次方和。由于这个结果可能非常大，输出其对998244353取模的结果。
树的节点从1开始标号，其中1号节点为树的根。
输出
对于每组数据输出一行一个正整数表示取模后的结果。
样例输入
5
1 2
1 3
2 4
2 5
2
1 4 5
5 4 45
样例输出
33
503245989
提示
以下用d(i)表示第i个节点的深度。
对于样例中的树，有d(1)=0,d(2)=1,d(3)=1,d(4)=2,d(5)=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。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
const int mod=;
vector<int> a[];
int fa[],b[maxn],n,k;
ll sum[maxn][],ans;
queue<int> rec;
void init()//预处理每个点的1-50次方
{
for(int i=; i<=n; i++)
{
for(int j=; j<=; j++)
{
if(j==) sum[i][j]=b[i];
else sum[i][j]=sum[i][j-]*b[i]%mod;
}
}
}
void digui(int r,int t)//关键部分，递归求路径所有点的k次方
{
if(b[r]<b[t])
{
ans=(ans+sum[t][k])%mod;
digui(r,fa[t]);
}
else if(b[r]>b[t])
{
ans=(ans+sum[r][k])%mod;
digui(fa[r],t);
}
else if(b[r]==b[t]&&fa[r]==fa[t]&&r!=t)
{
ans=(ans+sum[r][k])%mod;
ans=(ans+sum[t][k])%mod;
ans=(ans+sum[fa[r]][k])%mod;
return ;
}
else if(r==t)
{
ans=(ans+sum[r][k])%mod;
return ;
}
else if(b[r]==b[t]&&fa[r]!=fa[t])
{
ans=(ans+sum[r][k])%mod;
ans=(ans+sum[t][k])%mod;
digui(fa[r],fa[t]);
}
}
int read()//读入挂，输入有点多
{
int x=,f=;
char c=getchar();
while((c<'' || c>'') && c!=EOF)
{
if(c=='-') f=-;
c=getchar();
}
while((c<='' && c>='') && c!=EOF)
{
x=x*+c-'';
c=getchar();
}
return x*f;
}
void bfs(int x)//bfs求深度
{
for(int i=; i<a[x].size(); i++)
{
if(b[a[x][i]]==&&a[x][i]!=)
{
fa[a[x][i]]=x;//顺便记录一下父节点
b[a[x][i]]=b[x]+;
rec.push(a[x][i]);
} }
}
int main()
{
n=read();
fa[]=;//attention!
int p,q,cnt=,T,st,en;
for(int i=; i<n; i++)//vector建边
{
p=read();
q=read();
a[p].push_back(q);
a[q].push_back(p);
}
rec.push();
b[]=;//attention!
while(cnt>)
{
p=rec.front();
bfs(p);
rec.pop();
cnt=rec.size();
}
init();
T=read();
while(T--)
{
st=read();
en=read();
k=read();
ans=;
digui(st,en);
printf("%lld\n",ans);
}
return ;
}