/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 900 点
問題文
整数列 A = (A_2,A_3,\ldots,A_N) があります。また、各 i (2 \leq i \leq N) について 1 \leq P_i \leq i-1 を満たす整数列 P=(P_2, P_3, \ldots ,P_N) に対して、頂点 1 を根とする N 頂点の重み付き木 T(P) を以下のように定義します。
- 各 i (2 \leq i \leq N) について、i の親が P_i であり、i と P_i を結ぶ辺の重みが A_i であるような根付き木
Q 個のクエリが与えられるので、順に処理してください。i 番目のクエリは以下の通りです。
- 1 以上 N 以下の整数 u_i,v_i が与えられる。P としてあり得る (N-1)! 通りの数列全てについての木 T(P) での頂点 u_i と頂点 v_i の距離の総和を 998244353 で割った余りを出力する。ただし、頂点 u_i と頂点 v_i の距離とは、この 2 頂点を結ぶ唯一の（同じ頂点を 2 回以上通らない）パスに含まれる辺の重みの総和である。
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq u_i \lt v_i \leq N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_2 A_3 \ldots A_N u_1 v_1 u_2 v_2 \vdots u_Q v_Q
出力
Q 行出力せよ。i 行目には、i 番目のクエリの答えを出力せよ。
入力例 1
3 2 1 1 1 2 1 3
出力例 1
2 3
- P = (1,1) の場合、木 T(P) での頂点 1 と頂点 2 の距離は 1、頂点 1 と頂点 3 の距離は 1 です。
- P = (1,2) の場合、木 T(P) での頂点 1 と頂点 2 の距離は 1、頂点 1 と頂点 3 の距離は 2 です。
以上より、全ての P に対する木 T(P) での頂点 1 と頂点 2 の距離の総和は 2、頂点 1 と頂点 3 の距離の総和は 3 です。
入力例 2
2 1 100 1 2
出力例 2
100
入力例 3
9 6 765689282 93267307 563699854 951829154 801512848 389123318 924504746 596035433 3 8 2 5 5 8 2 9 8 9 5 7
出力例 3
55973424 496202632 903509579 343265517 550981449 68482696
総和を 998244353 で割った余りを求めることに注意してください。
Score : 900 points
Problem Statement
There is an integer sequence A = (A_2,A_3,\ldots,A_N). Also, for an integer sequence P=(P_2, P_3, \ldots ,P_N) where 1 \leq P_i \leq i-1 for each i (2 \leq i \leq N), define the weighted tree T(P) with N vertices, rooted at vertex 1, as follows:
- A rooted tree where, for each i (2 \leq i \leq N), the parent of i is P_i, and the weight of the edge between i and P_i is A_i.
You are given Q queries. Process them in order. The i-th query is as follows:
- You are given integers u_i and v_i, each between 1 and N. For each of the possible (N-1)! sequences P, take the tree T(P) and consider the distance between vertices u_i and v_i in this tree. Output the sum, modulo 998244353, of these distances over all T(P). Here, the distance between two vertices u_i and v_i is the sum of the weights of the edges on the unique path (not visiting the same vertex more than once) that connects them.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq u_i < v_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q A_2 A_3 \ldots A_N u_1 v_1 u_2 v_2 \vdots u_Q v_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
3 2 1 1 1 2 1 3
Sample Output 1
2 3
- If P = (1,1), then in the tree T(P), the distance between vertices 1 and 2 is 1, and the distance between vertices 1 and 3 is 1.
- If P = (1,2), then in the tree T(P), the distance between vertices 1 and 2 is 1, and the distance between vertices 1 and 3 is 2.
Therefore, the total distance between vertices 1 and 2 over all T(P) is 2, and the total distance between vertices 1 and 3 over all T(P) is 3.
Sample Input 2
2 1 100 1 2
Sample Output 2
100
Sample Input 3
9 6 765689282 93267307 563699854 951829154 801512848 389123318 924504746 596035433 3 8 2 5 5 8 2 9 8 9 5 7
Sample Output 3
55973424 496202632 903509579 343265517 550981449 68482696
Remember to take the sum modulo 998244353.