Background

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.

Problem Description

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

Input Format

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 Format

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

3
1 1
1 2
1
1 3 2

1 2

5
1 1
1 2
3 3
2 4
9
2 5 497855355
1 5 840823564
3 1 295265328
2 3 457999227
4 4 235621825
2 1 86836399
5 2 800390742
5 3 869167938
2 4 269250165

405260353 409046983 606499796 13504540

Hint

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.

For all testdata, it is guaranteed that $1\leq n,m\leq5000$, $1\leq l_i\leq r_i<i$, $1\leq u_i,v_i\leq n$, and $1\leq w_i\leq 10^9$.

Translated by ChatGPT 5