You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

楼下说得对，但是 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$。

数据规模与约定

本题采用捆绑测试。

对于所有数据，保证 $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$。