对于一个操作 $(u,v,w)$，钦定 $u<v$，那么对 $(fa(v),v)$ 的权值有 $w$ 的贡献。

剩下的部分交给 $fa(v) \in [L(v),R(v)]$。处理，对于每一种父亲期望贡献权值 $\frac{w}{R(v)-L(v)+1}$，这是一个子问题。

具体来说这类似一个动态规划，$f(i,j)$ 表示 $(i,j)$ 的期望权值（钦定 $i<j$），按照上面的说法转移即可。

$$
f(k,i) = f(k,i) + \frac{f(i,j)}{R(j)-L(j)+1}
$$

注意到我们钦定 $k<i$ 所以转移类似于一个 L 字型的区域加上一个定值。

我们可以二维差分来优化。

由于我们的转移方向是从大到小的，所以我们的差分方向也从大到小，这样我们就可以比较好求前缀和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000;
const int mod=998244353;
int n,m;
int inv[maxn+5];
int L[maxn+5],R[maxn+5];
int f[maxn+5][maxn+5];
int ans[maxn+5];
inline int Fpow(int x,int y){
    int res=1;
    for(;y;x=1ll*x*x%mod,y>>=1)
        if(y&1) res=1ll*res*x%mod;
    return res;
}
inline void Modify(int lx,int rx,int ly,int ry,int v){
    lx--,ly--;
    f[rx][ry]=(f[rx][ry]+v)%mod;
    f[rx][ly]=(f[rx][ly]-v)%mod;
    f[lx][ry]=(f[lx][ry]-v)%mod;
    f[lx][ly]=(f[lx][ly]+v)%mod;
}
signed main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) inv[i]=Fpow(i,mod-2);
    for(int i=2;i<=n;i++) scanf("%d%d",&L[i],&R[i]);
    scanf("%d",&m);
    int u,v,w;
    while(m--){
        scanf("%d%d%d",&u,&v,&w);
        if(u==v) continue;
        if(u>v) swap(u,v);
        Modify(u,u,v,v,w);
    }
    for(int i=n;i>=1;i--){
        for(int j=n;j>=1;j--){
            f[i][j]=(0ll+f[i][j]+f[i+1][j]+f[i][j+1]-f[i+1][j+1])%mod;
            if(i<j){
                if(L[j]<=i) Modify(L[j],min(i,R[j]),i,i,1ll*f[i][j]*inv[R[j]-L[j]+1]%mod);
                if(i<=R[j]) Modify(i,i,max(L[j],i),R[j],1ll*f[i][j]*inv[R[j]-L[j]+1]%mod);
            }
        }
    }
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ans[j]=(ans[j]+f[i][j])%mod;
    for(int i=2;i<=n;i++) printf("%d ",(ans[i]+mod)%mod);
    return 0;
}