树形dp
\(dp[u][k][0/1]\) 表示以 \(u\) 为根的子树,有 \(k\) 个感染的结点,无 / 有感染源的概率
统计答案的时候要乘上父节点不被传染的概率,表示只传染该子树,不蔓延到父节点那边
这个状态设计是默认根一定被感染
看了下别人的源码,改了一种树形 \(dp\) 的风格
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 2010;
vector<vector<int>>gra;
vector<ll>w, p, siz;
ll dp[maxn][maxn][2], ans[maxn];
ll inv(ll x)
{
ll ans = 1, n = mod - 2;
while(n)
{
if(n & 1) ans = ans * x % mod;
x = x * x % mod;
n >>= 1;
}
return ans % mod;
}
vector<ll>dp0(maxn, 0), dp1(maxn, 0);
void dps(int now, int pre)
{
dp[now][1][1] = w[now];
dp[now][1][0] = p[now];
dp[now][0][0] = (1 - p[now] + mod) % mod;
siz[now] = 1;
for(int nex : gra[now])
{
if(nex == pre) continue;
dps(nex, now);
for(int i=1; i<=siz[now]; i++)
{
for(int j=0; j<=siz[nex]; j++)
{
dp1[i + j] += (dp[now][i][0] * dp[nex][j][1] + dp[now][i][1] * dp[nex][j][0]) % mod;
dp0[i + j] += dp[now][i][0] * dp[nex][j][0] % mod;
}
}
siz[now] += siz[nex];
for(int i=1; i<=siz[now]; i++)
{
dp[now][i][0] = dp0[i] % mod;
dp[now][i][1] = dp1[i] % mod;
dp0[i] = dp1[i] = 0;
}
}
for(int i=1; i<=siz[now]; i++) ans[i] = (ans[i] + dp[now][i][1] * dp[pre][0][0]) % mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
gra.resize(n + 1);
w.resize(n + 1);
p.resize(n + 1);
siz.resize(n + 1);
for(int i=1; i<n; i++)
{
int a, b;
cin >> a >> b;
gra[a].push_back(b);
gra[b].push_back(a);
}
ll sum = 0;
for(int i=1; i<=n; i++)
{
ll a, b, c;
cin >> a >> b >> c;
sum += a;
p[i] = b * inv(c) % mod;
w[i] = a;
}
sum = inv(sum);
for(int i=1; i<=n; i++) w[i] = w[i] * sum % mod;
dp[0][0][0] = 1;
dps(1, 0);
for(int i=1; i<=n; i++) cout << ans[i] << "\n";
return 0;
}
原文地址:http://www.cnblogs.com/dgsvygd/p/16890392.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性