I Infection

知识点: 树上背包

第一次写树上背包的题目，没想到就是在区域赛中
神奇的是树上背包的复杂度，看起来是\(O(n^3)\)，但是实际计算只有\(O(n^2)\)

学会树上背包后可以很明显^[1]的发现这是一道树上背包的题目
而我认为该题思路的难点^[2]在于想到先枚举被感染的点集，再确定起始感染点是哪一个
所以我们就可以定义dp状态：
1.该点集是否包含起始感染点
2.以u为根的子树
3.该点集内被感染的点数
如果已经学过树上背包，此时就十分好转移了

#include<bits/stdc++.h>
using namespace std;
#define rep(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
template<class T> using vc = vector<T>;
template<class T> using vvc = vc<vc<T>>;

const int mod = 1e9 + 7;
const int N = 2e3 + 5;

ll dp[2][N][N];

ll ksm(ll x, int n)
{
    ll ret = 1;
    while (n)
    {
        if (n & 1) ret = ret * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return ret;
}
vc<int> h[N];
ll p[N], w[N], ans[N];
int sz[N];


void dfs(int u, int fa)
{
    dp[0][u][0] = 1 - p[u]; //未选择初始感染点,u子树,0个感染点
    dp[0][u][1] = p[u];     //未选择初始感染点,u子树,1个感染点
    dp[1][u][1] = w[u];     //选择u为初始感染点,1个感染点

    sz[u] = 1;  //已合并节点个数
    
    for (auto v : h[u])
    {
        if (v == fa) continue;
        dfs(v, u);

        vc<ll> dp0(sz[u] + sz[v] + 1, 0), dp1(sz[u] + sz[v] + 1, 0);
        rep(i, 1, sz[u]) rep(j, 0, sz[v])
        {
            dp0[i + j] = (dp0[i + j] + dp[0][u][i] * dp[0][v][j]) % mod;
            dp1[i + j] = (dp1[i + j] + dp[1][u][i] * dp[0][v][j] + dp[0][u][i] * dp[1][v][j]) % mod;   
        }
        sz[u] += sz[v];
        //更新dp状态
        rep(i, 1, sz[u])
        {
            dp[0][u][i] = dp0[i];
            dp[1][u][i] = dp1[i];
        }
    }
    //统计答案
    rep(i, 1, sz[u]) ans[i] = (ans[i] + dp[1][u][i] * (1 - p[fa])) % mod;
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    //init
    int n; cin >> n;
    rep(i, 2, n)
    {
        int u, v; cin >> u >> v;
        h[u].push_back(v);
        h[v].push_back(u);
    }
    ll wi(0);
    rep(i, 1, n)
    {
        int a, b, c;
        cin >> a >> b >> c;
        wi += w[i] = a;
        p[i] = b * ksm(c, mod - 2) % mod;
    }
    wi = ksm(wi, mod - 2);
    rep(i, 1, n) w[i] = w[i] * wi % mod;

    //树上背包
    dfs(1, 0);

    //输出答案
    rep(i, 1, n) cout << (ans[i] % mod + mod) % mod << endl;
    return 0;
}

M XOR Sum

先占坑