CTS2019

CTS/CTSC2019

只是象征性的选了几道计数题做,并不是完整的题解。

随机立方体

直接做好像不太星,考虑容斥。

\(f[i]\)表示至少有\(i\)个极大的数的方案数,\(N = n \times m \times l\)。则有: \[ f[i]=\binom{N}{g[i]}b[i]\times h[i]\times (N - g[i])! \] \(b[i]\)表示选出\(i\)个三维坐标都不相同的点的方案数。(\(i\)个极大的数)

\(g[i]\)表示和\(i\)个极大的数中任意一个至少有一维坐标相同的点的个数。

\(h[i]\)表示将\(g[i]\)个数字分配给\(g[i]\)的个点的合法分配的方案数。(合法指的是\(i\)个极大的数可以同时存在)

我们一个一个考虑。

考虑\(b[i]\)怎么算:

你每选择出来一个点\((x_0,y_0,z_0)\)并钦定它为极大的,\(x=x_0,y=y_0,z=z_0\)这三个平面上的点都不能再作为极大的点了,相当于立方体从\(n \times m \times l\)变成了\((n-1)\times (m-1)\times (l-1)\)。所以显然有: \[ b[i] =\frac{1}{i!}\prod_{j=0}^{i-1}(n-j)\times(m-j)\times(l-j) \] 考虑\(g[i]\)怎么算:

都知道\(b[i]\)怎么算了,显然有 \[ g[i]=n\times m\times l-(n-i)\times (m-i)\times (l-i) \] 考虑\(h[i]\)怎么算:

设需要比第\(i\)个极大的点要小的点上数字集合为\(S_i\)\(a[i]\)表示第\(i\)个极大的点上的数字。

我们先钦定\(i\)个极大的点上的数字的大小关系。我们由数字从小到大的顺序依次考虑这个\(i\)个极大的点。考虑加入第\(j\)个极大的点后方案数的变化:

因为新加入极大的点\(j\)比已经加入的\(j-1\)个极大的点都要大,所以有: \[ a[j] > k, \forall k\in {S_j{\large\cap} S_r}(r\in [1,j-1]) \] 所以我们只用考虑:\(S_j\)和前\(j-1\)极大的点的集合不交的部分。并且这部分和前\(j-1\)个极大的点的集合的交集没有明确的大小关系。设\(S_i\)和前\(i-1\)个集合的并集的不交部分的大小为\(R\),则有: \[ h[i]=h[i-1]\times \left(\left|{\large\cup}_{j=1}^{i-1}S_j\right|+1\right)^{\overline{R}} \] PS:\(x^{\overline{n}}\)表示\(x\)\(n\)次上升幂。

并且有\(R=g[i]-g[i-1], \left|{\large\cup}_{j=1}^{i-1}S_j\right| = g[i]\)。所以: \[ \begin{aligned}h[i]&=h[i-1]\times (g[i-1]+1)^{\overline{g[i]-g[i-1]}}\\&=h[i-1] \times \frac{(g[i]-1)!}{g[i-1]!}\\&=\prod_{j=1}^i\frac{(g[j]-1)!}{g[j-1]!}\end{aligned} \] 记得最后我们对于\(h[i]\)还要乘上\(i\)的阶乘,因为一开始我们钦定了大小顺序。

然后把所有的东西都代回去,则有: \[ \begin{aligned}f[i]&=\binom{N}{g[i]}b[i]\times i!\prod_{j=1}^i\frac{(g[j]-1)!}{g[j-1]!}\times (N - g[i])!\\&=\frac{N!}{(N-g[i])!g[i]!}\times i!\prod_{j=1}^i\frac{(g[j]-1)!}{g[j-1]!}\times (N - g[i])!\times b[i]\end{aligned} \] 发现我们最后算概率的时候要乘上\(\frac{1}{N!}\)并且式子的最后有一个\((N-g[i])!\),则有: \[ \begin{aligned}f[i]&=\frac{i!}{g[i]!}\times \prod _{j=1}^i\frac{(g[j]-1)!}{g[j-1]!}\\&=i!\prod_{j=1}^i\frac{(g[j]-1)!}{g[j]!}\\&=i!\prod_{j=1}^i\frac{1}{g[j]}\end{aligned} \] 最后二项式反演一下有: \[ ans = \sum_{i=k}^{\min(n,m,l)}(-1)^{i-k}\binom{i}{k}f[i] \]

然后有因为我们最多只能选出\(\min(n,m,l)\)个极大的点并且要求一个\(g[i]\)的逆元,所以现在复杂度为\(O(T\min(n,m,l)\log P)\)。可以获得\(80\)分的好成绩....

然后这个地方我们有一个小\(\text{trick}\):我们预处理出来\(g[i]\)的前缀积,求最后一项的逆元后可以逆推每一个前缀积的逆元....就和逆推阶乘的逆元是一个道理。最终复杂度为\(O(T\min(n,m,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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
* 3119.cpp
* This file is part of 3119
*
* Copyright (C) 2019 - ViXbob
*
* 3119 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.
*
* 3119 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 3119. 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))
#define getd(i) (1ll * (n - (i)) * (m - (i)) % P * (l - (i)) % P)

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int maxn = 5e6 + 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, m, l, k, N, T, c[maxn], g[maxn], h[maxn], f[maxn], ifac[maxn], fac[maxn], mn, b[maxn], pre[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 C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % 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;
}

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
T = read(); fac[0] = 1;
rep(i, 1, maxn - 1) fac[i] = 1ll * fac[i - 1] * i % P;
ifac[maxn - 1] = inv(fac[maxn - 1]);
dep(i, maxn - 2, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;
while(T--) {
n = read(); m = read(); l = read(); k = read(); h[0] = 1; b[0] = 1; pre[0] = 1;
N = n * m * l; mn = min(n, min(m, l));
// rep(i, 1, mn) c[i] = (n - i + 1) * (m - i + 1) * (l - i + 1) - (n - i) * (m - i) * (l - i);
rep(i, 1, mn) g[i] = pls(g[i - 1], dec(getd(i - 1), getd(i)));
rep(i, 1, mn) pre[i] = 1ll * pre[i - 1] * g[i] % P;
// g[i] = nml - (n - i) * (m - i) * (l - i)
//
rep(i, 1, mn) b[i] = 1ll * b[i - 1] * getd(i - 1) % P;
// rep(i, 1, mn) g[i] = g[i - 1] + getd(i - 1) - getd(i);
// h[1] = fac[g[1] - 1];
// rep(i, 1, mn) h[i] = 1ll * h[i - 1] * fac[g[i] - 1] % P * ifac[g[i - 1]] % P;
// rep(i, 1, mn) f[i] = 1ll * b[i] * h[i] % P * fac[N - g[i]] % P * C(N, g[i]) % P;
// rep(i, 1, mn) h[i] = 1ll * h[i - 1] * inv(g[i]) % P;
pre[mn] = inv(pre[mn]);
dep(i, mn, 1) pre[i - 1] = 1ll * pre[i] * g[i] % P;
rep(i, 1, mn) f[i] = 1ll * b[i] * pre[i] % P;
int ans = 0;
rep(i, k, mn) if((i - k) & 1) ans = dec(ans, 1ll * C(i, k) * f[i] % P);
else ans = pls(ans, 1ll * C(i, k) * f[i] % P);
cout << 1ll * ans % P << endl;
}
return 0;
}

珍珠

这道题好像对不会生成函数的选手不太友好啊....(比如我)

\(cnt[i]\)表示第\(i\)种颜色的珠子的数量,那么就变成了求\(\sum_{i=1}^D[cnt[i] \bmod 2] \le n-2m\)的序列的个数。然后这个显然可以\(\text{dp}\),不过有两种:

第一种:

\(f[i][j][k]\)表示考虑了前\(i\)种珠子一共选出了\(j\)个,为个数为奇数的珠子的种数为\(k\)\(\frac{1}{\prod_{j=1}^icnt[j]}\)的和。

最后答案直接就是: \[ n!\sum_{i=0}^{n-2m}f[D][n][i] \] 这个东西嘛,珠子显然都是等价的,转移又是个卷积,应该是可以多项式快速幂的。(我当时是这么想得,但是并不会处理后面的那个奇偶)

复杂度\(O(D^3n)\)

第二种:

显然状态不需要这么暴力,设\(f[i][j]\)表示选了\(i\)个珠子有\(j\)种珠子的个数为奇数的方案数。显然有转移: \[ \begin{cases}f[i][j] \times (D-j) \to f[i+1][j+1]&j \le D\\f[i][j] \times j \to f[i+1][j-1]&j>0\end{cases} \] 复杂度\(O(Dn)\),矩阵快速幂优化一下就是\(O(D^3\log n)\)。但我不懂\(\text{laofu}\)那档\(D \le 300\)的部分分是什么意思,考怎么卡常吗?

然后第二种\(\text{dp}\)好像就没什么优化空间了。然后我也就不会了。转战题解

到处学习了一下姿势发现第一种\(\text{dp}\)有很大的优化空间。

如果把第一种\(\text{dp}\)值搞成生成函数,那么转移显然就是卷上\(e^x\)。但是后面的奇偶的东西要容斥一下。

然后我们先了解一些神奇的\(\text{EGF}\)\[ e^{-x}=\sum_{i=0}^{\infin}(-1)^{i}\frac{x^i}{i!} \]

\[ \frac{e^{x}-e^{-x}}{2}=\sum_{i=0}^{\infin}\frac{x^{2i+1}}{(2i+1)!} \]

\[ \frac{e^{x}+e^{-x}}{2}=\sum_{i=0}^{\infin}\frac{x^{2i}}{(2i)!} \]

\(f[i]\)表示至少有\(i\)种珍珠的个数为奇数的\(\frac{1}{\prod_{j=1}^icnt[j]}\)的和。

\(g[i]\)表示恰好有\(i\)种珍珠的个数为奇数的\(\frac{1}{\prod_{j=1}^icnt[j]}\)的和。

则有: \[ \begin{aligned}f[i]&=\binom{D}{i}[x^n]\left(\frac{e^x-e^{-x}}{2}\right)^ie^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n](e^x-e^{-x})^ie^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}e^{jx}e^{(j-i)x}e^{(D-i)x}\\&=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{i-j}e^{(D-2(i-j))x}\end{aligned} \] 然后把里面的\(j\)设成\(i-j\)等式不变。 \[ f[i]=\frac{1}{2^i}\binom{D}{i}[x^n]\sum_{j=0}^i\binom{i}{j}(-1)^{j}e^{(D-2j)x} \] 然后现在又有一个神奇的\(\text{EGF}\)\[ e^{cx}=\sum_{i=0}^{\infin}c^i\frac{x^i}{i!} \] 又因为最后答案要乘上\(n\)的阶乘,我们现在先乘进去: \[ \begin{aligned}f[i]&=\frac{1}{2^i}\binom{D}{i}\sum_{j=0}^i\binom{i}{j}(-1)^j(D-2j)^n\\\frac{f[i]}{i!}&=\frac{1}{2^i}\binom{D}{i}\sum_{j=0}^i\frac{(-1)^j(D-2j)^n}{j!}\frac{1}{(i-j)!}\end{aligned} \] 显然是个卷积的形式。

最后二项式反演一下有: \[ \begin{aligned}g[i]&=\sum_{j=i}^D(-1)^{j-i}\binom{j}{i}f[j]\\g[i] \times i!&=\sum_{j=i}^D\frac{(-1)^{j-i}}{(j-i)!}f[j]\times j!\end{aligned} \] 然后我们把\(g[i] \times i!\)\(f[i] \times i!\)\(\text{reverse}\)一下就是一个卷积的形式了。最后答案为: \[ \sum_{i=0}^{n-2m}g[i] \] 复杂度为\(O(D \log D)\)

PS : 要先判一下\(n - 2m < 0\)\(n - 2m \ge D\)的情况。

代码:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*
* 3120.cpp
* This file is part of 3120
*
* Copyright (C) 2019 - ViXbob
*
* 3120 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.
*
* 3120 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 3120. 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 = 1e5 + 5;
const int P = 998244353;
const int inf = 0x3f3f3f3f;
const int maxm = maxn << 2;

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 D, n, m, ans, fac[maxn], ifac[maxn], f[maxn], g[maxn], ipow2[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 C(int n, int m) { return 1ll * fac[n] * ifac[m] % P * ifac[n - m] % 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;
}

namespace NTT {
const int G = 3, invG = inv(G);

int s, l, rev[maxm], E[maxm], H[maxm], inv;

inline void init(int n) {
s = 2; l = 1;
while(s <= n) s <<= 1, l++; inv = inv(s);
rep(i, 0, s - 1) rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
memset(E, 0, sizeof(int) * (s + 5));
memset(H, 0, sizeof(int) * (s + 5));
}

inline void dft(int *a, int n, int f) {
rep(i, 0, n - 1) if(i < rev[i]) swap(a[i], a[rev[i]]);
for(int i = 1; i < n; i <<= 1) {
int Wn = ksm(f, (P - 1) / (i << 1));
for(int j = 0; j < n; j += (i << 1)) {
int w = 1;
for(int k = 0; k < i; k++, w = 1ll * w * Wn % P) {
int A1 = a[j + k], A2 = 1ll * w * a[j + k + i] % P;
a[j + k] = pls(A1, A2); a[j + k + i] = dec(A1, A2);
}
}
}
}

inline void conv() {
dft(E, s, G); dft(H, s, G);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * H[i] % P;
dft(E, s, invG);
rep(i, 0, s - 1) E[i] = 1ll * E[i] * inv % P;
}
}

const int inv2 = inv(2);

int main() {
// freopen("1.in", "r", stdin);
// freopen("my.out", "w", stdout);
D = read(); n = read(); m = read();
if(n - 2 * m < 0) { cout << 0 << endl; return 0; }
if(n - 2 * m >= D) { cout << ksm(D, n) << endl; return 0; }
fac[0] = 1; ipow2[0] = 1;
rep(i, 1, D) fac[i] = 1ll * fac[i - 1] * i % P, ipow2[i] = 1ll * ipow2[i - 1] * inv2 % P;
ifac[D] = inv(fac[D]);
dep(i, D - 1, 0) ifac[i] = 1ll * ifac[i + 1] * (i + 1) % P;

NTT :: init(D << 1);
for(int i = 0, ty = 1; i <= D; i++, ty = (ty == 1 ? P - 1 : 1))
NTT :: E[i] = 1ll * ty * ksm(pls(D - 2 * i, P), n) % P * ifac[i] % P, NTT :: H[i] = ifac[i];
NTT :: conv();
rep(i, 0, D) f[i] = 1ll * ipow2[i] * fac[i] % P * C(D, i) % P * NTT :: E[i] % P;

NTT :: init(D << 1);
for(int i = 0, ty = 1; i <= D; i++, ty = (ty == 1 ? P - 1 : 1))
NTT :: E[i] = 1ll * f[D - i] * fac[D - i] % P, NTT :: H[i] = 1ll * ty * ifac[i] % P;
NTT :: conv();
rep(i, 0, D) g[i] = 1ll * NTT :: E[D - i] * ifac[i] % P;
rep(i, 0, n - 2 * m) ans = pls(ans, g[i]);
cout << ans << endl;
return 0;
}
/*
*/

无处安放

题答题先咕着...

田野

我是计算几何垃圾,只会凸包,告辞。

重复

做不动了,坑先挖着。顺便膜拜rqy。

氪金手游

一开始\(\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)\)

代码:

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
/*
* 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;
}