「CTS 2019」氪金手游【容斥原理 + 树形 DP】

Time Limit: 1 Sec Memory Limit: 512 MB

Description

小刘同学最近迷上了一个新游戏,游戏的内容就是不断地抽卡。现在已知:

  • 卡池里总共有 nn 种卡,第 ii 种卡有一个权值 WiW_i。小刘同学不知道 WiW_i 具体的值是什么,但是 WiW_i 服从一个分布。
  • 具体地,对每个 ii 有三个参数 pi,1,pi,2,pi,3p_{i, 1}, p_{i, 2}, p_{i, 3}WiW_i 将会以 pi,jp_{i, j} 的概率取值为 jj,保证和为 11

小刘每次会氪一元钱来抽一张卡,其中抽到卡 ii 的概率为:

WijWj\frac{W_i}{\sum_j W_j}

小刘会不停地抽卡,直到他手里集齐了全部 nn 种卡。抽卡结束后,记录下来了第一次得到每张卡的时间 {Ti}\{ T_i \}。有 n1n - 1 个二元组 (ui,vi)(u_i, v_i),对于任意的 ii 都必须满足 Tui<TviT_{u_i} < T_{v_i}

保证将所有的 uiu_iviv_i 连边后,形成一棵树 (ui(u_i 不一定是 viv_i 的父亲))

求小刘同学满足条件的概率,输出所求概率对 998244353998244353 取模的结果。

Input

第一行一个整数 nn,表示卡的种类数。

接下来 nn 行,每行三个整数 ai,1,ai,2,ai,3a_{i, 1}, a_{i, 2}, a_{i, 3},而题目给出的 pi,j=ai,jai,1+ai,2+ai,3p_{i, j} = \frac{a_{i, j}}{a_{i, 1} + a_{i, 2} + a_{i, 3}}

接下来 n1n - 1 行,每行两个整数 ui,viu_i, v_i,描述一个二元组。

Output

输出一行一个整数,表示所求概率对 998244353998244353 取模的结果。

Sample Input

1
2
3
4
2
0 0 1
1 1 0
1 2

Sample Output

1
524078286

Hint

W2W_212\frac{1}{2} 的概率取 11 或者 22

  • 如果 W2=1W_2 = 1T1<T2T_1 < T_2 的概率为 34\frac{3}{4}
  • 如果 W2=2W_2 = 2T1<T2T_1 < T_2 的概率为 35\frac{3}{5}

所以概率为 12(34+35)=2740\frac{1}{2} \big( \frac{3}{4} + \frac{3}{5} \big) = \frac{27}{40},对 998244353998244353 取模即为所给答案。

Constraints

对于全部的数据,满足 n1000,n \leqslant 1000, ai,j106a_{i, j} \leqslant 10^6

  • 子任务 11 (20(\text{20}))n15n \leqslant 15
  • 子任务 22 (15(15))n200,n \leqslant 200, uivi=1\lvert u_i - v_i \rvert = 1
  • 子任务 33 (20(20))n1000,n \leqslant 1000, uivi=1\lvert u_i - v_i \rvert = 1
  • 子任务 44 (15(15))n200n \leqslant 200
  • 子任务 55 (30(30)):无特殊限制。

Solution

首先考虑一条链 12n1 \to 2 \to \cdots \to n 的特殊情况:

ans=P(1n)=i=1nWij=inWj\text{ans} = P(1 \to n) = \prod_{i = 1}^n \frac{W_i}{\sum_{j = i}^n W_j}

再考虑链上只有一条反向边时 ((1k(k+1)n)1 \to \cdots \to k \leftarrow (k + 1) \to \cdots \to n)

ans=P(1k)P((k+1)n)P(1n)\text{ans} = P(1 \to k) \cdot P\big( (k + 1) \to n \big) - P(1 \to n)

考虑将链推广到外向树,设 f(i,j)f(i, j) 表示子树 iiWi=j\sum W_i = j 时合法的概率。如果有反向边,那么 P(P(反向边)) == P(P(不存在这条边的限制)) - P(P(正向边))。时间复杂度为 O(n2)O(n^2)

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
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1010, P = 998244353;
int n, ans, f[maxn][maxn * 3], inv[maxn * 3], sz[maxn];
struct edge { int to, mul; };
vector<edge> G[maxn];
void add(int &x, int y) { if ((x += y) >= P) x -= P; }

int qp(int x, int y) {
int z = 1;
for (; y; y >>= 1, x = 1LL * x * x % P) {
if (y & 1) z = 1LL * z * x % P;
}
return z;
}

void dfs(int v, int fa) {
sz[v] = 3;
for (int i = 0, u; i < G[v].size(); i++) {
if ((u = G[v][i].to) == fa) continue;
dfs(u, v);
for (int x = sz[v]; x; x--) {
int old = f[v][x]; f[v][x] = 0;
for (int y = sz[u]; y; y--) {
add(f[v][x + y], 1LL * old * f[u][y] % P * G[v][i].mul % P);
if (G[v][i].mul ^ 1) add(f[v][x], 1LL * old * f[u][y] % P);
}
}
sz[v] += sz[u];
}
for (int x = 1; x <= sz[v]; x++) {
f[v][x] = 1LL * f[v][x] * inv[x] % P;
}
}

int main() {
scanf("%d", &n);
for (int i = 1, a1, a2, a3, s; i <= n; i++) {
scanf("%d %d %d", &a1, &a2, &a3);
f[i][1] = 1LL * a1 * (s = qp(a1 + a2 + a3, P - 2)) % P;
f[i][2] = 2LL * a2 * s % P, f[i][3] = 3LL * a3 * s % P;
}
for (int i = 1; i <= n * 3; i++) {
inv[i] = qp(i, P - 2);
}
for (int i = 1, u, v; i < n; i++) {
scanf("%d %d", &u, &v);
G[u].push_back((edge){v, 1});
G[v].push_back((edge){u, P - 1});
}
dfs(1, 0);
for (int i = 1; i <= sz[1]; i++) {
add(ans, f[1][i]);
}
printf("%d\n", ans);
return 0;
}