【题解】[CTS2019] 氪金手游
题目链接：[CTS2019] 氪金手游
题意：
给定一棵 $n$ 个节点的树，每条边定向。每个节点有一个权值 $w_i\in\{1,2,3\}$，$w_i=j$ 的概率为 $p_{i,j}$。
第 $i$ 个点在卡池中放 $w_i$ 个，每次等概率从卡池中取出一个点。求 $n$ 个点被首次抽出的顺序，满足树上边的方向的概率。
$1\le n\le 10^3$
考虑如果树的定向方式是一棵外向树该怎么做。发现合法的情况下，$n$ 个点被首次抽出的顺序构成树的一个拓扑序。但每个节点在卡池中个数可能不同，所以无法直接套用树的拓扑序的式子。
但是可以魔改，对于以 $i$ 为根的子树，要求 $i$ 首次抽出的时间比子树内任何节点首次抽出的时间要早。设 $\text{sub}(i)$ 表示 $i$ 的子树，则合法方案数应为：
$$ \dfrac{\dfrac{((\sum_{j\in\text{sub}(i)} w_j)-1)!}{(w_i-1)!\prod_{j\in\text{sub}(i),j\ne i} w_j!}}{\dfrac{(\sum_{j\in\text{sub}(i)} w_j)!}{\prod_{j\in\text{sub}(i)} w_j!}} $$
$$ =\dfrac{w_i}{\sum_{j\in\text{sub(i)}} w_j} $$
因此可以设 $\text{dp}_{i,j}$ 表示在 $i$ 的子树中，子树 $w$ 之和为 $j$ 的情况下，合法的概率。
再考虑非外向树的情形。考虑往外向树的情形进行转化，因此可以进行容斥。将 “内向” 转变为 “不定向” $-$ “外向”。
对于一条内向边 $(x,\text{fa}_x)$，在考虑他不定向的情形的时候，则 $x$ 子树内的 $w$ 之和与 $\text{fa}_x$ 没有关系了，所以这个子树的贡献需要删去，表示不考虑这条边的限制。
对于一组方案，如果有 $k$ 条内向边被我们设置为外向，则意味着至少 $k$ 条内向边被设置为外向。因为有一些被设置为不定向的内向边也可能是外向的。
因此，如果有 $k$ 条内向边被我们设置为外向，其容斥系数为 $(-1)^k$。
容易设出 $\text{dp}$。设 $\text{dp}_{i,j,k}$ 表示 $i$ 子树内，子树 $w$ 之和为 $j$，子树内有 $k$ 条内向边被设置为外向的情况下，合法的概率。
实际上，我们并不需要记录 $k$ 一维。因为我们发现，当我们在某一个状态上，多设置一条内向边为外向的时候，其容斥系数恰好 $\times (-1)$。所以我们只需要将这个 $-1$ 在 $\text{dp}$ 转移的时候乘上就行。
因此方程变为：设 $\text{dp}_{i,j}$ 表示 $i$ 子树内，子树 $w$ 和为 $j$ 的情况下，所有方案的概率乘上其容斥系数的和。容易使用背包转移的方式做到 $\mathcal{O}(n^2)$。
//Code By CXY07
#include<bits/stdc++.h>
using namespace std;
//#define FILE
#define int long long
#define file(FILENAME) freopen(FILENAME".in", "r", stdin), freopen(FILENAME".out", "w", stdout)
#define randint(l, r) (rand() % ((r) - (l) + 1) + (l))
#define LINE() cout << "LINE = " << __LINE__ << endl
#define debug(x) cout << #x << " = " << x << endl
#define abs(x) ((x) < 0 ? (-(x)) : (x))
#define inv(x) qpow((x), mod - 2)
#define lowbit(x) ((x) & (-(x)))
#define ull unsigned long long
#define pii pair<int, int>
#define LL long long
#define mp make_pair
#define pb push_back
#define scd second
#define vec vector
#define fst first
#define endl '\n'
const int MAXN = 3010;
const int INF = 2e9;
const double eps = 1e-6;
const double PI = acos(-1);
//const int mod = 1e9 + 7;
const int mod = 998244353;
//const int G = 3;
//const int base = 131;
int n, m, Ans;
int p[MAXN][4], siz[MAXN], Inv[MAXN];
int dp[MAXN][MAXN], tmp[MAXN];
vec<pii> G[MAXN];
template<typename T> inline bool read(T &a) {
a = 0; char c = getchar(); int f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') {a = a * 10 + (c ^ 48); c = getchar();}
return a *= f, true;
}
template<typename A, typename ...B>
inline bool read(A &x, B &...y) {return read(x) && read(y...);}
int qpow(int x, int b) {
int res = 1;
for(; b; b >>= 1, (x *= x) %= mod) if(b & 1) (res *= x) %= mod;
return res;
}
void DFS(int x, int f) {
siz[x] = 3;
for(int i = 1; i <= 3; ++i) dp[x][i] = p[x][i] * i % mod;
for(auto to : G[x]) {
if(to.fst == f) continue;
DFS(to.fst, x);
for(int j = 1; j <= siz[x]; ++j)
for(int k = 1, coe; k <= siz[to.fst]; ++k) {
coe = dp[x][j] * dp[to.fst][k] % mod;
if(to.scd == 1) (tmp[j + k] += coe) %= mod;
else (tmp[j + k] += mod - coe) %= mod, (tmp[j] += coe) %= mod;
}
siz[x] += siz[to.fst];
for(int j = 1; j <= siz[x]; ++j) dp[x][j] = tmp[j], tmp[j] = 0;
}
for(int j = 1; j <= siz[x]; ++j) dp[x][j] = dp[x][j] * Inv[j] % mod;
}
signed main () {
#ifdef FILE
freopen(".in", "r", stdin);
freopen(".out", "w", stdout);
#endif
read(n); Inv[1] = 1;
for(int i = 2; i <= (n * 3); ++i)
Inv[i] = Inv[mod % i] * (mod - mod / i) % mod;
for(int i = 1, s; i <= n; ++i) {
s = 0;
for(int j = 1; j <= 3; ++j) read(p[i][j]), s += p[i][j];
s = inv(s);
for(int j = 1; j <= 3; ++j) p[i][j] = p[i][j] * s % mod;
}
for(int i = 1, x, y; i < n; ++i) {
read(x), read(y);
G[x].pb(mp(y, 1)), G[y].pb(mp(x, 0));
}
DFS(1, 0);
for(int i = 1; i <= siz[1]; ++i) (Ans += dp[1][i]) %= mod;
printf("%lld\n", Ans);
return 0;
}