• 欢迎光临~

# 2021 陕西省赛 D - Disease // 树形概率dp

(g_i) 的事件实际上是，前 (i-1) 层不存在染病结点，且第 (i) 层存在染病结点。

(ans = sumlimits_{i=1}^{maxDepth}i times prodlimits_{depth_{large j} < i} (1-frac{large p_j}{large q_j}) times (prodlimits_{depth_{large j} = i} (1 - f_j · frac{large a_j}{large b_j}) - prodlimits_{depth_{large j} = i}f_j)) .

``````#include <bits/stdc++.h>
#define endl 'n'
#define int long long
using namespace std;

const int N = 100010;
const int mod = 1e9 + 7;

int n, dep[N], f[N], p[N], q[N];
vector<pair<int,int>> g[N];
vector<int> vec[N];

int qmi(int m, int k, int p)
{
int res = 1;
while(k) {
if(k & 1) res = res * m % p;
m = m * m % p;
k >>= 1;
}
return res;
}

int getmod(int x)
{
return (x % mod + mod) % mod;
}

int dfs(int u, int fa) {
if(~f[u]) return f[u];
vec[dep[u]].push_back(u);
f[u] = getmod(1 - p[u]);
for(auto e : g[u]) {
int v = e.first, w = e.second;
if(v == fa) continue;
dep[v] = dep[u] + 1, q[v] = w;
int p1 = dfs(v, u);
int p2 = getmod(1 - dfs(v, u)) * getmod(1 - w) % mod;
f[u] = f[u] * (p1 + p2) % mod;
}
return f[u];
}

signed main()
{
cin.tie(0);
ios::sync_with_stdio(false);

cin >> n;
for(int i = 1; i <= n; ++ i) {
int x, y;
cin >> x >> y;
p[i] = x * qmi(y, mod - 2, mod) % mod;
}
for(int i = 1; i < n; ++ i) {
int u, v, a, b;
cin >> u >> v >> a >> b;
int w = a * qmi(b, mod - 2, mod) % mod;
g[u].push_back({v, w}), g[v].push_back({u, w});
}

memset(f, -1, sizeof f);
dep[1] = 1, dfs(1, -1);

int ans = 0, P = 1;
for(int i = 1; i <= n; ++ i) {
if(!vec[i].size()) break;
int res = P, P1 = 1, P2 = 1;
for(auto x : vec[i]) {
P = P * getmod(1 - p[x]) % mod;
P1 = P1 * getmod(1 - getmod(1 - f[x]) * q[x] % mod) % mod;
P2 = P2 * f[x] % mod;
}
res = res * getmod(P1 - P2) % mod;
ans = (ans + res * i) % mod;
}
cout << ans << endl;

return 0;
}
``````