I Infection

知识点: 树上背包

第一次写树上背包的题目,没想到就是在区域赛中
神奇的是树上背包的复杂度,看起来是$O(n3)$,但是实际计算只有$O(n2)$

学会树上背包后可以很明显[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

先占坑


  1. 当起始感染点被确定后,其它点被感染只有当其父亲被感染时才会被感染 ↩︎

  2. 也可能只是我菜,写的题太少没见过 ↩︎

原文地址:http://www.cnblogs.com/lunasama/p/16890445.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性