P7247 Textbook Delivery

“If Tianyi comes to volunteer, she might die from exhaustion.” ------------ “Where on earth is Class 3, Grade 7 again...”, the little gray-haired girl panted and complained, still refusing to give up. Sweat gathered in her hair, lazily resting on her pale neck, and the sticky feeling faintly drew a picture of heat in her mind. Dozens of textbooks pressed against her chest. With both hands stretched straight in front of her thighs, she supported the heavy weight with difficulty, and inched up the long stairs step by step along the handrail. Behind her, a cute tuft of brown “ahoge” bounced up happily, “So\~ do you need help?”

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$.

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$.

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

------------ #### 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$. | Subtask | Points | $n$ | Special constraints | | :-----: | :----: | :------------------: | :----------------------------------------: | | 1 | 5 | $ \le 3$ | / | | 2 | 10 | $ \le 13$ | / | | 3 | 10 | $ \le 20$ | / | | 4 | 25 | $ \le 5\times 10^3 $ | / | | 5 | 5 | / | For $\forall 1\le i\le n$, $a_i=1$. | | 6 | 10 | / | For every edge, $v_i=u_i+1$, i.e. the tree is a chain. | | 7 | 35 | / | / | Translated by ChatGPT 5