\(CCPC2022\)广州\(I\)
这是一道和队友\(vp\)时我没有出的\(dp\)题目，说明我的\(dp\)还有很多空缺，加练！
题意
一种高度繁殖的细菌感染了一棵由 \(n\) 个节点（有 \(n-1\)条边，无循环）组成的树。这些节点的索引从 \(1\)到 \(n\)。
一开始正好有一个节点被感染。树上的每个节点都有一个初始易感性权重 \(a_i\)，表示节点\(i\)有 \(\dfrac{a_i}{\sum_{i=1}^{n}a_i}\)的概率成为树的初始感染节点。
此外，每个节点都有一个感染概率 \(p_i\)，表示其被相邻节点感染的概率。
具体来说，从初始感染节点开始，如果一个节点被感染，与其相邻的未感染节点 \(x\)将有概率 \(p_x\)成为新的感染节点，然后 \(x\)可以继续感染其相邻节点。
现在，您的任务是计算恰好有 \(k\)个节点最终被感染的概率。你需要为每个 \(k=1,\ldots, n\)输出一个答案。
如果答案是 \(\frac{a}{b}\)( \(\gcd(a,b)=1\))，则需要输出 \(a\cdot b^{-1}\bmod{10^9+7}\)，其中 \(b\cdot b^{-1} \equiv 1 \pmod{10^9+7}\)。
题解
如果对于一个根结点，我们去考虑它下面的点分别要设计多少个点被传染，那么我们就还需要考虑它的下面的下面的结点设计多少个结点被感染，这样子的做法无疑是非常差的做法，而且肯定超时。
那么，遇到这类求所有情况的题目，我们可以采用树上背包的思想来考虑这道题，甚至不需要换根。
首先，我们对于一个图来进行讨论，不妨就用样例好了。
对于我们的\(2\)号点，假如它先遍历到了\(3\)号点，那么我们先计算答案，再把\(3\)号结点下面的节点数加给\(2\)号结点
在遍历到\(3\)号点之前，以\(2\)号点为根的子树结点只有自己，以\(3\)为根的子树下面结点数为\(2\)
设计状态
那么我们可以考虑两种状态，
第一种，目前状态下(就是说这个点下面的结点不一定统计完了)\(3\)号点里面有\(i\)个传染点，且没有感染源
第二种，目前状态下(就是说这个点下面的结点不一定统计完了)\(3\)号点里面有\(i\)个传染点，且有传染源
那么，我们可以设立两个状态数组\(f[i][j]\)和\(g[i][j]\)，\(f\)表示第一种状态，\(g\)则表示第二种状态
其次，我们再建立一个计数数组\(siz[i]\)，表示目前状态下此时\(i\)号点为根的树的结点个数
初始状态
\(f[u][1] = a[u] * invb[u]\)
\(g[u][1] = p[u]*inv\)
状态转移(满足乘法原理)
现在再回到题目，我们先讨论\(2\)号点当前状态：
- 没有感染源
\(f[2][1] = f[3][1] * f[2][0] + f[3][0] * f[2][1]\)
\(f[2][2] = f[3][1] * f[2][1] + f[3][2] * f[2][0] + f[3][0] * f[2][2]\)
你会发现，可能会出现计算错误的情况，所以我们需要两个中转数组记录答案，再转移
\(f[u][v] = \sum_{div}^{u}(f[u][i]*f[div][j]),(i + j =v,div\in u)\) - 有感染源
\(g[2][1] = (g[2][1] * f[3][0] + f[2][1] * g[3][0]) + (g[2][0] * f[3][1] + f[2][0] * g[3][1])\)
\(g[2][2] = (g[2][1] * f[3][1] + f[2][1] * g[3][1]) + (g[3][2] * f[2][0] + f[3][2] * g[2][0]) + (g[3][0] * f[2][2] + f[3][0] * g[2][2])\)
因为其中一个里面有感染源，但是不确定是哪棵树的，所以我们分情况讨论
\(g[u][v] = \sum_{div}^{u}(f[u][i] * g[div][j] + g[u][i]*f[div][j]),(i + j = v,div\in u)\)
结合答案
我们的答案要求输出所有的情况，所以，我们需要将最后结果统计到\(res\)数组中，假设我们现在遍历到\(u\)结点，它的父亲是\(fa\)
\(res[i] = res[i] + g[u][i] * (1 - a[fa] * invb[fa]);\)
传染源和感染病毒都在\(u\)号点为根的树中，那么它的父节点必不可能是传染源，那么将父亲不被传染的概率乘上\(g[u][i]\)即可，这也是不需要换根的奥妙，我们将感染源限制住了。
代码实现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int P = 1e9 + 7;
const int N = 2010;
//存图
int ne[N << 1], e[N << 1], h[N << 1], idx;
//上面解释过了
int f[N][N], g[N][N], siz[N], res[N];
//中转数组
int t1[N], t2[N];
//预处理变量
int p[N], a[N], b[N], inva[N], invb[N], inv, sum;
int n, m;
void add(int x, int y) {
ne[idx] = h[x], e[idx] = y, h[x] = idx++;
}
int qmi(int x, int k, int p) {
int res = 1;
while(k) {
if(k & 1) res = res * x % p;
x = x * x % p;
k >>= 1;
}
return res;
}
void dfs(int u, int fa) {
//初始化
siz[u] = 1;
f[u][1] = a[u] * invb[u] % P;
g[u][1] = p[u] * inv % P;
for(int i = h[u];i != -1;i = ne[i]) {
int div = e[i];
if(div == fa) continue;
dfs(div, u);
//记录数组
memset(t1, 0, sizeof(t1));
memset(t2, 0, sizeof(t2));
//树上背包
for(int j = siz[u] + siz[div];j >= 0;j--) {
for(int k = max(0ll, j - siz[u]);k <= min(j, siz[div]);k++) {
t1[j] = (t1[j] + f[u][j - k] * f[div][k] % P) % P;
t2[j] = (t2[j] + g[u][j - k] * f[div][k] % P + f[u][j - k] * g[div][k] % P) % P;
}
}
siz[u] += siz[div];
//记录答案
for(int i = 0;i <= siz[u];i++) {
f[u][i] = t1[i];
g[u][i] = t2[i];
}
}
//上面遍历可能会改变这个值，我们重新赋值即可
f[u][0] = (1 - a[u] * invb[u] % P + P) % P;
//计算全部概率
if(u != 1) {
//其他点有父结点
for(int i = 1;i <= n;i++) {
res[i] = (res[i] + g[u][i] * (1 - a[fa] * invb[fa] % P) % P) % P;
}
}
else {
//1号点没有父节点
for(int i = 1;i <= n;i++) {
res[i] = (res[i] + g[u][i]) % P;
}
}
}
void solve() {
cin >> n;
memset(h, -1, sizeof(h));
for(int i = 1;i < n;i++) {
int x, y;
cin >> x >> y;
add(x, y), add(y, x);
}
//预处理
for(int i = 1;i <= n;i++) {
cin >> p[i] >> a[i] >> b[i];
sum += p[i];
inva[i] = qmi(a[i], P - 2, P);
invb[i] = qmi(b[i], P - 2, P);
}
inv = qmi(sum, P - 2, P);
dfs(1, 0);
for(int i = 1;i <= n;i++) cout << (res[i] + P) % P << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int T = 1;
while(T -- ) {
solve();
}
return 0;
}