\(\mathcal{Description}\)
Link.
有 \(n\) 张卡牌,第 \(i\) 张的权值 \(w_i\in\{1,2,3\}\),且取值为 \(k\) 的概率正比于 \(p_{i,k}\)。依照此规则确定权值后,你不停抽卡,每次抽到第 \(i\) 张卡牌的概率正比于 \(w_i\),直到所有卡都被抽过至少一次。
此后,记 \(t_i\) 表示第 \(i\) 张牌第一次被抽到的时间。给定 \(n-1\) 条形如 \(\lang u,v\rang\) 的限制,表示 \(t_u<t_v\),保证 \(\lang u,v\rang\) 构成的有向图的基图是一棵树。得到的 \(\{t_n\}\) 满足限制的概率,答案模 \(998244353\)。
\(n\le10^3\)。
\(\mathcal{Solution}\)
其实是 trick + 板子,但是没见过的话使得想一会儿。
考虑若树是严格外向树怎么做,这时点 \(u\) 要满足的条件有且仅有「对于所有 \(u\) 子树内的结点 \(v\),\(t_u<t_v\)」。设 \(u\) 子树内的点权和已经确定为 \(s_u\),\(w_u\) 也已确定,则概率显然为 \(\frac{w_u}{s_u}\)。继而得到 DP:令 \(f(u,i)\) 表示 \(u\) 子树内点权和为 \(i\) 时,子树内合法的概率,转移时需要注意 \(\frac{w_u}{s_u}\) 需要转化成条件概率(或者除掉再把新的乘上去)。
接下来走进一般情况,仍然如外向树般,钦定一个根 \(r\),把指向 \(r\) 的边理解为外向树边“反向”,对于这些边,如果按照正常的外向树做 DP,就相当于「钦定这条限制不合法」;如果忽略这条边,就相当于「这条限制不一定合法」,最后能得到「至少有一些限制不合法」,那么带着容斥系数做 DP 就行。复杂度 \(\mathcal O(wn^2)\)。
\(\mathcal{Code}\)
/*+Rainybunny+*/
#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l, rep##i = r; i <= rep##i; ++i)
#define per(i, r, l) for (int i = r, per##i = l; i >= per##i; --i)
const int MAXN = 1e3, MOD = 998244353;
int ecnt = 1, n, m, head[MAXN + 5], pr[MAXN + 5][3], inv[MAXN * 3 + 5];
int siz[MAXN + 5], f[MAXN + 5][MAXN * 3 + 5];
struct Edge { int to, nxt; } graph[MAXN * 2 + 5];
inline void link(const int u, const int v) {
graph[++ecnt].to = v, graph[ecnt].nxt = head[u], head[u] = ecnt;
graph[++ecnt].to = u, graph[ecnt].nxt = head[v], head[v] = ecnt;
}
inline void subeq(int& u, const int v) { (u -= v) < 0 && (u += MOD); }
inline int mul(const int u, const int v) { return 1ll * u * v % MOD; }
inline int sub(int u, const int v) { return (u -= v) < 0 ? u + MOD : u; }
inline void addeq(int& u, const int v) { (u += v) >= MOD && (u -= MOD); }
inline int add(int u, const int v) { return (u += v) < MOD ? u : u - MOD; }
inline int mpow(int u, int v) {
int ret = 1;
for (; v; u = mul(u, u), v >>= 1) ret = mul(ret, v & 1 ? u : 1);
return ret;
}
inline void solve(const int u, const int fa) {
siz[u] = 1;
rep (i, 1, 3) f[u][i] = mul(i, pr[u][i - 1]);
for (int i = head[u], v; i; i = graph[i].nxt) {
if ((v = graph[i].to) != fa) {
solve(v, u);
static int tmp[MAXN * 3 + 5];
rep (j, 1, siz[u] * 3) rep (k, 1, siz[v] * 3) {
int t = mul(f[u][j], f[v][k]);
if (i & 1) subeq(tmp[j + k], t), addeq(tmp[j], t);
else addeq(tmp[j + k], t);
}
siz[u] += siz[v];
rep (j, 1, siz[u] * 3) f[u][j] = tmp[j], tmp[j] = 0;
}
}
rep (i, 1, siz[u] * 3) f[u][i] = mul(f[u][i], inv[i]);
}
int main() {
scanf("%d", &n);
rep (i, 1, n) {
int s = 0;
rep (j, 0, 2) scanf("%d", &pr[i][j]), s += pr[i][j];
s = mpow(s, MOD - 2);
rep (j, 0, 2) pr[i][j] = mul(s, pr[i][j]);
}
rep (i, 2, n) {
int u, v; scanf("%d %d", &u, &v);
link(u, v);
}
inv[1] = 1;
rep (i, 2, 3 * n) inv[i] = mul(inv[MOD % i], MOD - MOD / i);
solve(1, 0);
int ans = 0;
rep (i, 1, siz[1] * 3) addeq(ans, f[1][i]);
printf("%d\n", ans);
return 0;
}