F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:替用户ir1d发布如下信息,希望大家能够积极支持。 OI Wiki 致力于成为一个开放自由的 OI 知识整合站点,欢迎感兴趣的同学参与贡献 https://oi-wiki.org
Problem 5293. -- [Bjoi2018]求和

5293: [Bjoi2018]求和

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 299  Solved: 172
[Submit][Status][Discuss]

Description

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

Input

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

Output

对于每组数据输出一行一个正整数表示取模后的结果。
1≤n,m≤300000,1≤k≤50

Sample Input

5
1 2
1 3
2 4
2 5
2
1 4 5
5 4 45

Sample Output

33
503245989
说明
样例解释
以下用d(i) 表示第i 个节点的深度。
对于样例中的树,有d(1)=0,d(2)=1,d(3)=1,d(4)=2,d(5)=2。
因此第一个询问答案为(2^5 + 1^5 + 0^5) mod 998244353 = 33
第二个询问答案为(2^45 + 1^45 + 2^45) mod 998244353 = 503245989。

HINT

Source

鸣谢佚名上传

[Submit][Status][Discuss]

HOME Back