P10879 "KDOI-07" Love for Heavy-Light Decomposition

The person downstairs is right, but in NOI 2024 D2T2, sszcdjr used a clever method to defeat my brute-force heavy-light decomposition. The person upstairs is right, but heavy-light decomposition got me to $10\sqrt{}$, so I made this problem to show my love for heavy-light decomposition.

You are given a rooted tree with $n$ nodes, rooted at $1$. For each node $2\leq i\leq n$, its parent $f_i$ is chosen uniformly at random from $[l_i,r_i]$. Each edge of the tree has an edge weight, initially $0$. Now there are $m$ operations. The $i$-th operation adds $w_i$ to the weights of all edges on the path from $(u_i,v_i)$. After all $m$ operations, for all $i=2\sim n$, compute the expected value of the weight on edge $(i,f_i)$, modulo $998244353$.

The first line contains one positive integer $n$. In the next $n-1$ lines, the $i$-th line contains two positive integers $l_{i+1},r_{i+1}$. The next line contains one positive integer $m$. In the next $m$ lines, the $i$-th line contains three positive integers $u_i,v_i,w_i$.

Output one line with $n-1$ positive integers. The $i$-th integer denotes the expected edge weight of edge $(i+1,f_{i+1})$, modulo $998244353$.

### Sample Explanation 1 There are $2$ possible cases for the parents of all nodes: - $f_2=1,f_3=1$. In this case, the edge weights on $(f_2,2),(f_3,3)$ are $0,2$, respectively. - $f_2=1,f_3=2$. In this case, the edge weights on $(f_2,2),(f_3,3)$ are $2,2$, respectively. So the expected edge weight of $(f_2,2)$ is $\dfrac{0+2}{2}=1$, and the expected edge weight of $(f_3,3)$ is $\dfrac{2+2}{2}=2$. --- ### Constraints **This problem uses bundled testdata.** | $\text{Subtask}$ | $n\leq$ | $m\leq$ | Score | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $10$ | $20$ | | $2$ | $50$ | $50$ | $20$ | | $3$ | $500$ | $500$ | $20$ | | $4$ | $5000$ | $1$ | $20$ | | $5$ | $5000$ | $5000$ | $20$ | For all testdata, it is guaranteed that $1\leq n,m\leq5000$, $1\leq l_i\leq r_i