「KDOI-07」对树链剖分的爱

楼下说得对，但是 sszcdjr 在 NOI 2024 D2T2 用巧妙做法把我的暴力树剖爆掉了。 楼上说得对，但是树链剖分把我送上 10√ 了，所以我出了这道题以表示我对树链剖分的爱喵。

给出一棵 $n$ 个节点以 $1$ 为根的有根树。对于第 $2\leq i\leq n$ 个节点，其父亲 $f_i$ 在 $[l_i,r_i]$ 中均匀随机。每个树的边有边权，初始为 $0$。 现在有 $m$ 次操作，第 $i$ 次操作表示将 $(u_i,v_i)$ 的路径上所有的边的权值统一加上 $w_i$。$m$ 次操作结束后，对于所有 $i=2\sim n$，求 $(i,f_i)$ 边上权值的期望，对 $998244353$ 取模。

第一行一个正整数表示 $n$。 接下来 $n-1$ 行，其中第 $i$ 行两个正整数表示 $l_{i+1},r_{i+1}$。 接下来一行一个正整数表示 $m$。 接下来 $m$ 行，第 $i$ 行三个正整数表示 $u_i,v_i,w_i$。

一行 $n-1$ 个正整数，其中第 $i$ 个表示边 $(i+1,f_{i+1})$ 边权的期望，对 $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

### 样例解释 1 所有节点的父亲共有 $2$ 种可能的情况： - $f_2=1,f_3=1$，此时 $(f_2,2),(f_3,3)$ 边上的权值分别是 $0,2$。 - $f_2=1,f_3=2$，此时 $(f_2,2),(f_3,3)$ 边上的权值分别是 $2,2$。 于是边 $(f_2,2)$ 边权的期望为 $\dfrac{0+2}{2}=1$，边 $(f_3,3)$ 边权的期望为 $\dfrac{2+2}{2}=2$。 --- ### 数据规模与约定 **本题采用捆绑测试。** | $\text{Subtask}$ | $n\leq$ | $m\leq$ | 分数 | | :-----------: | :-----------: | :-----------: | :-----------: | | $1$ | $10$ | $10$ | $20$ | | $2$ | $50$ | $50$ | $20$ | | $3$ | $500$ | $500$ | $20$ | | $4$ | $5000$ | $1$ | $20$ | | $5$ | $5000$ | $5000$ | $20$| 对于所有数据，保证 $1\leq n,m\leq5000$，$1\leq l_i\leq r_i<i$，$1\leq u_i,v_i\leq n$，$1\leq w_i\leq 10^9$。