TSS '19 CC P4 - Power Sum on a Tree

View as PDF

Submit solution

Points: 15
Time limit: 4.0s
Memory limit: 512M

Problem type

Given a tree with N nodes, conveniently numbered from 1 to N, node 1 is the root node. You need to answer Q queries. Each query is in the form u v k, which is \sum{ \text{depth(i)} ^ k} where node i is on the path from u to v, i.e. adding up the k-th power of the depth of each node along the path from u to v.

Input Specification

The first line contains one integer, N, (1 \le N \le 300,000), the number of nodes in the tree.

Each of the following N-1 lines contains two integers, u and v (1 \le u, v \le N), an edge between u and v.

The next line contains one integer, Q, (1 \le Q \le 300,000), the number of queries.

Each of the following Q lines contains three integers, u, v, and k, (1 \le u, v \le N, 1 \le k \le 50).

Output Specification

Print one integer for each query, the sum modulo 998244353.

Sample Input

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

Sample Output

33
17

Explanation

For the tree in the sample input, the depth of each node is: dep[1] = 0, dep[2] = 1, dep[3] = 1, dep[4] = 2, dep[5] = 2.

For the first query, the path is 1-->2-->4. Thus, the sum is  (0^5 + 1^5 + 2^5) \mod 998244353 = 33.

For the second query, the path is 5-->2-->4. Thus, the sum is (2^{3} + 1^{3} + 2^{3}) \mod 998244353 = 17.


Comments

There are no comments at the moment.