自动搬运

查看原文

来自洛谷，原作者为

	ViXbob **

搬运于2025-08-24 22:10:26，当前版本为作者最后更新于2019-05-19 23:48:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

滋磁去我的博客看吖

一开始$\text{naive}$了，以为二元组$u_i \to v_i$连出来的一定是一颗外向树。后来发现有反边。

我索性先来考虑一下外向树的这种情况吧。对于第$i$个点设其子树的$w_i$和为$Sw$, 所有点的和为$Sum$。因为除了$i$子树中的点要比$i$晚抽到外，剩余所有的点都可比$i$早抽到。所以$i$比子树中的所有卡牌都要早抽到的概率为：

$$\begin{aligned}&\frac{w_i}{Sum}\sum_{i=0}^n\left(\frac{Sum-Sw}{Sum}\right)^i\\=&\frac{w_i}{Sum}\times \frac{Sum}{Sw}=\frac{w_i}{Sw}\end{aligned} $$

这个只与子树信息有关。我们考虑设计状态$f_{i,j}$表示处理完$i$这个子树，子树中$w_i$和为$j$的概率和。转移直接背包就好了。

然后考虑反向边：

反向边我们不好直接处理，考虑容斥。反向边的若干个二元组就是一些条件而已我们想要它们都满足，直接大力容斥有：

至少$0$个条件不满足$-$至少一个条件不满足$+$至少两个条件不满足$-\cdots$

我们发现至少$i$个不满足就是选择任意$i$条反向边后将这些边反向，另外的边删掉(不考虑这些条件就是至少)。这样会构成一个外向树森林。我们枚举每一条反向边的状态后也可以$\text{dp}$，复杂度$O(2^nn^2)$。

考虑优化一下这个过程，我们其实没有必要知道是每条边具体的状态，我们只用考虑最后被反向的反向边的个数，我们直接把这个东西压入状态，设$f_{i,j,k}$表示处理完$i$的子树后子树$w_i$和为$j$，被反向的反向边的个数为$k$的概率和。(注意到由反向边相连的子树的大小视为$0$)最终的复杂度为$O(n^3)$。

实际上我们没有必要最后用第三维状态$k$来统计答案(计算容斥系数)，可以直接在$\text{dp}$转移中就直接考虑容斥系数就好了，选择一条反向边并将其反向实则就是将$\text{dp}$乘上$-1$，然后就可以直接转移了。复杂度$O(n^2)$。

代码：

/*
 * 3124.cpp
 * This file is part of 3124
 *
 * Copyright (C) 2019 - ViXbob
 *
 * 3124 is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Lesser General Public
 * License as published by the Free Software Foundation; either
 * version 2.1 of the License, or (at your option) any later version.
 *
 * 3124 is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License
 * along with 3124. If not, see <http://www.gnu.org/licenses/>.
 */

/**
 * There is no end though there is a start in space. ---Infinity.
 * It has own power, it ruins, and it goes though there is a start also in the star. ---Finite.
 * Only the person who was wisdom can read the most foolish one from the history.
 * The fish that lives in the sea doesn't know the world in the land.
 * It also ruins and goes if they have wisdom.
 * It is funnier that man exceeds the speed of light than fish start living in the land.
 * It can be said that this is an final ultimatum from the god to the people who can fight.
 *
 * Steins;Gate
 */
#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = j; i <= k; ++i)
#define dep(i, j, k) for(int i = j; i >= k; --i)
#define SIZE(x) ((int)x.size())
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define inv(x) (ksm(x, P - 2))

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 1e3 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;

inline int read() {
	char ch = getchar(); int u = 0, f = 1;
	while(!isdigit(ch)) { if(ch == '-') f = -1; ch = getchar(); }
	while(isdigit(ch))  { u = u * 10 + ch - 48; ch = getchar(); } return u * f;
}

int n, a[maxn], b[maxn], c[maxn], s[maxn], f[maxn][maxn * 3], rt, size[maxn], ans, tmp[maxn * 3];
int inv[maxn * 3];
vector<pair<int, int> > G[maxn];

inline int pls(int x, int y) { x += y; return x >= P ? x - P : x; }
inline int dec(int x, int y) { x -= y; return x < 0 ? x + P : x; }
inline int mul(int x, int y) { return 1ll * x * y % P; }
inline int ksm(int x, int k, int rnt = 1) { 
	for(int i = k; i; i >>= 1, x = 1ll * x * x % P) if(i & 1) rnt = 1ll * rnt * x % P;
	return rnt;
}

inline void dfs(int x, int fr) {
	size[x] = 1;
	f[x][1] = 1ll * a[x] * s[x] % P;
	f[x][2] = 1ll * b[x] * s[x] % P * 2 % P;
	f[x][3] = 1ll * c[x] * s[x] % P * 3 % P;
	for(auto v : G[x]) if(v.first != fr) {
		dfs(v.first, x);
		rep(i, 1, size[x] * 3) rep(j, 1, size[v.first] * 3) {
			int res = 1ll * f[x][i] * f[v.first][j] % P;
			if(v.second) tmp[i + j] = dec(tmp[i + j], res), tmp[i] = pls(tmp[i], res);
			else tmp[i + j] = pls(tmp[i + j], res);
		}
		size[x] += size[v.first];
		rep(i, 1, 3 * size[x]) f[x][i] = tmp[i], tmp[i] = 0;
	}
	rep(i, 1, size[x] * 3) f[x][i] = 1ll * f[x][i] * inv[i] % P;
}

int main() {
//	freopen("1.in", "r", stdin);
//	freopen("my.out", "w", stdout);
	n = read();
	rep(i, 1, 3 * n) inv[i] = inv(i);
	rep(i, 1, n) a[i] = read(), b[i] = read(), c[i] = read(), s[i] = inv(a[i] + b[i] + c[i]);
	rep(i, 1, n - 1) {
		int x = read(), y = read();
		G[y].pb(mp(x, 1)); G[x].pb(mp(y, 0));
	}
	dfs(1, 1);
	rep(i, 1, size[1] * 3) ans = pls(ans, f[1][i]);
	cout << ans << endl;
	return 0;
}