404043 - 求和

给定一棵以 1 号结点为根的 n 个结点的有根树。接下来进行 m 次询问，每次询问给出三个参数 u, v, k，要求计算树上从结点 u 到结点 v 的简单路径上，所有结点深度的 k 次方之和。结点深度定义为该结点到根结点的路径上的边数（根结点深度为 0）。由于答案可能非常大，请输出结果对 998244353 取模的值。

第一行一个正整数 n（1 ≤ n ≤ 3 ×105），表示树的结点数。 随后 n − 1 行，每行两个正整数 u, v，表示树上的一条无向边。 随后一行一个正整数 m，表示询问次数。 随后 m（1 ≤ m ≤ 3 ×105）行，每行三个正整数 u, v, k（1≤ k ≤ 50），表示一次询问。

共 m 行，每行一个整数，表示对应询问的答案（对 998244353 取模）。

以下用 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。 【数据范围】

对于 30% 的数据，1 ≤ n, m ≤ 100。

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