蚊子
描述
作为一只明媚的兔子，要会叠被子，又得会打蚊子……
兔子住在兔子洞里。兔子洞可以看成是一棵无根树，有 \(n\) 个洞穴，有 \(n-1\) 条通道连接着 \(n\) 个洞穴。每天晚上，兔子会在 \(1\) 号洞穴里缩成一团，睡一觉。同时，蚊子大军出动，去欺负兔子。
因为蚊子人多势众，所以它们分兵 \(m\times (m-1)\) 路。\(m\) 是整个兔子洞中只和一条通道相邻的洞穴数目。任意两个这样的洞穴 \(a,b\) 之间（也就是任意两个叶子节点之间）会有两只蚊子，一只从 \(a\) 飞到 \(b\)，一只从 \(b\) 飞到 \(a\)。它们都沿着 \(a\) 到 \(b\) 的最短路径移动。蚊子每秒钟可以通过一条通道。所有蚊子都在 \(0\)s 时突然出现在起点并开始移动。每只蚊子在到达终点后的一瞬间都会突然消失。有些蚊子并不会经过兔子所在的 \(1\) 号节点，它们起到的是恐吓作用。
又一次满脸是包地醒来后，兔子忍无可忍了，于是它找到 lrd，让 lrd 去打蚊子……lrd 不知所措，于是去某宝搞了一个灭蚊器……这个灭蚊器被放在 \(1\) 号节点。每个时刻，它都会工作一次，把和灭蚊器距离小于等于 \(d\) 范围内的蚊子全部杀死。（\(d=0\) 时只能控制 \(1\) 号点一个位置）
遗憾的是，兔子洞尚未通电，兔子只能用爱发电。 因此，每个时刻灭蚊器只有 \(\frac{p}{q}\) 的概率能够正常工作。如果不能正常工作，那么蚊子将不受到任何影响。
灭蚊器无法影响出现之前和消失之后的蚊子。但在蚊子出现在起点和消失在终点的
那个时刻，如果灭蚊器正常工作且蚊子在作用范围内，这只蚊子仍会被杀死。
兔子对 lrd 的诚意表示怀疑……于是它让 lrd 算出灭蚊器在一晚上期望能杀死多少蚊子。lrd 当然会算了，但是他想考考你。因为兔子讨厌小数，你需要输出这个期望值模 \(10^9+7\) 后的结果。即：表示为分子乘分母的逆元（对 \(10^9+7\) 取模）。
(如果你算错了，就会被 lrd 拿去喂兔子，啊呜~~)
格式
输入
第一行一个整数 \(n\)，表示兔子洞中洞穴的个数。洞穴编号为 \(1\) 到 \(n\) 的整数。
接下来 \(n-1\) 行，每行两个整数 \(u,v\)，表示 \(u\) 和 \(v\) 两个洞穴之间有一条通道。
接下来一行三个整数 \(d,p,q\)，表示灭蚊器的作用范围是 \(d\)，每个时刻工作的概率是 \(\frac{p}{q}\)。
输出
一行一个整数，你的答案。
样例
输入
3
1 2
1 3
1 1 2
输出
750000007
范围
| 编号 | 分值 | 特殊性质 |
|---|---|---|
| \(1\) | \(15\) | \(d=0\) |
| \(2\) | \(25\) | \(p=q\) |
| \(3\) | \(60\) | 无 |
对于所有测试点：
\(m<n\le 5000000,0\le d\le n,1\le p\le q\le 10^9+7\)
本文参考了 这篇题解 的思路，有不少补充。本文的代码与那篇题解的代码有不少相似之处，有不少细节改动。
解析
树形 DP 以及树上路径的好题。这个题目的部分分很有帮助价值。
先考虑 \(d=0\) 的情况，即只有根节点被灭蚊器控制。记 \(cnt_x\) 表示以 \(x\) 为根的子树的叶节点数量。令
\[sum=\sum_{i\in son_1} cnt_i \]\(son_i\) 表示 \(i\) 的子节点的集合。答案就是
\[\sum_{i\in son_1} cnt_i\times (sum-cnt_i) \]相当于，把根作为 LCA 折点，对于每一棵子树，都贡献了这棵子树叶子个数与非这棵子树叶子个数的乘积，相当于乘法原理的匹配。至于蚊子双向活动的问题，\(i\) 刷过一遍，每个叶子会在 \((sum-cnt_i)\) 中刷到，也会在 \(cnt_i\) 中刷到。乘上灭蚊器消杀概率即可。
再考虑满分做法。记录动态规划数组 \(f\)，\(f_i\) 表示所有蚊子在以 \(i\) 为根的子树里存活期望。同样的，令 \(w\) 为灭蚊器消杀概率：
\[sum=\sum_{v\in son_u} f_v \]\[tot=\sum_{v\in son_u} cnt_v \]以 \(u\) 为根的子树的贡献是：
\[\sum_{v\in son_u} cnt_v\times (tot-cnt_v)-f_v\times w\times (sum-f_v) \]还有一些细节。比如，题目中的分数取模，相当于乘上分母的逆元。灭蚊器消杀概率为 \(\frac{p}{q}\)，留蚊子活路的概率是
\[1-\frac{p}{q}=\frac{q-p}{q} \]可以全开 long long。
代码
// mosquito
#include <bits/stdc++.h>
#define int long long
#define SIZE 1000010
#define all(x) x.begin(), x.end()
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
int f[SIZE]={0}, dep[SIZE]={0}, cnt[SIZE]={0};
vector<int> a[SIZE]; int n, d;
int inv;
const int mod=1e9+7;
int val(int a, int b)
{
if(b==0) return 1%mod;
a%=mod;
int t=val(a, b/2);
if(b%2==0)
return t*t%mod;
return t*t%mod*a%mod;
}
void dfs(int u, int fa)
{
dep[u]=dep[fa]+1;
bool leaf=1;
for(int v:a[u])
{
if(v==fa) continue;
leaf=0;
dfs(v, u);
cnt[u]+=cnt[v];
if(dep[u]<=d+1) f[u]=(f[u]+f[v]*inv%mod)%mod;
else f[u]=(f[u]+f[v])%mod;
}
if(leaf)
{
cnt[u]=1;
if(dep[u]<=d+1) f[u]=inv;
else f[u]=1;
}
}
int ans=0;
void calc(int u, int fa)
{
if(dep[u]>d+1) return;
int sum=0, tot=0;
for(int v:a[u])
{
if(v==fa) continue;
sum=(sum+f[v])%mod; tot=(tot+cnt[v])%mod;
}
for(int v:a[u])
{
if(v==fa) continue;
ans=(ans+cnt[v]*(tot-cnt[v]+mod)%mod-(sum-f[v]+mod)*f[v]%mod*inv%mod+mod)%mod;
calc(v, u);
}
}
signed main()
{
freopen("mosquito.in", "r", stdin);
freopen("mosquito.out", "w", stdout);
scanf("%lld", &n);
for(int i=1; i<n; i++)
{
int u, v; scanf("%lld %lld", &u, &v);
a[u].push_back(v);
a[v].push_back(u);
}
int p, q; scanf("%lld %lld %lld", &d, &p, &q);
inv=(q-p)*val(q, mod-2)%mod;
dfs(1, 0);
calc(1, 0);
printf("%lld", ans);
return 0;
}