P6813 “MCOI-02” Glass

Xiao S entered a server. On this server there is a game called “Glass on a Tree”.

First, a tree is given. Each node has $V_i$ pieces of glass, and each edge has a weight $W_i$. In each operation, Xiao S can choose two nodes $u, v (u \ne v)$. On the unique path from node $u$ to node $v$, the **edge sum** is the sum of the weights of all edges on the path, i.e. $\sum W_i$. The **node sum** is the sum of the numbers of glass on all nodes on the path (including $u, v$), i.e. $\sum V_i$. Xiao S can obtain a score equal to the product of the **edge sum** and the **node sum**, i.e. $\sum W_i \times \sum V_i$. Any two operations cannot be exactly the same, and $(u, v)$ and $(v, u)$ are considered two different operations. However, sometimes the tree is too large, and Xiao S needs your help. He wants you to tell him: after $N(N-1)$ operations, how many points can be obtained in total. The result may be very large; you only need to output the answer modulo $998244353$.

The first line contains an integer $N$, denoting the number of nodes in the tree. The second line contains $N$ integers, where the $i$-th number $V_i$ denotes the number of glass at node $i$. The next $N-1$ lines each contain three numbers $x, y, z$, indicating that there is a tree edge between nodes $x$ and $y$ with weight $z$.

Output one integer, the total score modulo $998244353$.

#### Sample Explanation For sample $1$, the tree looks like this:  #### Constraints **This problem uses bundled testdata.** | Subtask ID | $N$ | $V_i, W_i$ | Special Property | Score | Time Limit | | :----------: | :----------: | :----------: | :----------: | :----------: | :----------: | | 1 | $\le 200$ | $\lt 2^3$ | | $3$ | $\rm 1s$ | | 2 | $\le 10^3$ | $\lt 2^3$ | | $6$ | $\rm 1s$ | | 3 | $\le 6 \times 10^3$ | $\lt 2^8$ | | $11$ | $\rm 1s$ | | 4 | $\le 2 \times 10^5$ | $\lt 2^8$ | There exists a node with degree $N-1$ | $12$ | $\rm 1s$ | | 5 | $\le 2 \times 10^5$ | | The tree is a chain | $13$ | $\rm 1s$ | | 6 | $\le 2 \times 10^5$ | | | $21$ | $\rm 1s$ | | 7 | $\le 2 \times 10^6$ | | | $34$ | $\rm 2s$ | For $100\%$ of the data, $0 \le V_i, W_i \lt 2^{16}$ and $1 \le N \le 2 \times 10^6$. #### Notes Minecraft OI Round 2 D - Maker: Inf_Voltage - Tester: tarjin Translated by ChatGPT 5