Description

The teaching building of Modu High School is a tree with $n$ nodes. Node $i$ corresponds to classroom $i$, with $a_i$ students. Each undirected edge $i$ is described as $(u_i,v_i,b_i)$, meaning it connects classrooms $u_i$ and $v_i$, and the stairs between them have a vertical height difference of $b_i\ \text{m}$.

At the beginning of the new semester, textbooks need to be distributed to students, but a failure in the teleportation system caused the textbooks to be scattered across different classrooms. When Tianyi is in classroom $u$, she will randomly pick up $a_v$ textbooks belonging to classroom $v~(v\in[1,n])$, and deliver them to classroom $v$ along the unique simple path between classrooms $u$ and $v$. Suppose the height differences of the stairs Tianyi walks through are $b_1,b_2,\cdots,b_m\ \text{m}$, and the weight of each textbook is $1\text{N}$. Then the absolute value of the work done by Tianyi’s lifting force during this delivery (taking positive work for going up and the absolute value of negative work for going down) is defined as $W=a_v\left( \sum_{i=1}^{m} b_i \right)\text{J}$. In other words, the cost of one delivery is the product of the endpoint node weight and the sum of edge weights along the path.

Initially, Tianyi is in classroom $1$, but she does not know the way, so Ayane will guide Tianyi to deliver textbooks such that Tianyi visits every classroom at least once. Before achieving this goal, what is the expected total absolute work done by Tianyi’s lifting force, in $\text{J}$?

Since the answer may be a decimal, to avoid precision loss, output the value of the answer modulo $998244353$.

Simplified statement

Given an unrooted tree with $n$ nodes, with node weights and edge weights. Let the current position be $s$ (initially $s=1$). Each time, randomly choose a target node $t$ among the $n$ nodes, pay a cost of (“sum of edge weights on the simple path from $s$ to $t$”) $\times$ (“node weight of $t$”), mark node $t$ (marking can repeat), and set $s=t$. Find the expected total cost when every node has been marked at least once (node $1$ is marked from the start). Output the answer modulo $998244353$.

Input Format

The first line contains an integer $n$, as described above.

The second line contains $n$ integers, representing the number of students in each classroom.

The next $n-1$ lines each contain three integers $u_i,v_i,b_i$, meaning there is a staircase with vertical height difference $b_i\ \text{m}$ between classrooms $u_i$ and $v_i$.

Output Format

One line with one integer, representing the answer modulo $998244353$.

3
1 2 3
1 2 1
2 3 1

332748127

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

615584181

2
1 2
1 2 2

4

Hint

Constraints and notes

This problem uses bundled testdata.

For $100\%$ of the testdata, $1\le n\le 10^6$, $1\le a_i,b_i\lt 998244353$, $1\le u_i,v_i\le n$, and it is guaranteed that $u_i\ne v_i$.

Translated by ChatGPT 5