P10879 「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$ 取模。

无

无

### 样例解释 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