题解 P5405 【[CTS2019]氪金手游】

ViXbob · 2019-05-19 23:48:57 · 题解

滋磁去我的博客看吖

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

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

这个只与子树信息有关。我们考虑设计状态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;
}