蚊子

描述

作为一只明媚的兔子，要会叠被子，又得会打蚊子……

兔子住在兔子洞里。兔子洞可以看成是一棵无根树，有 $n$$n$ 个洞穴，有 $n-1$$n-1$ 条通道连接着 $n$$n$ 个洞穴。每天晚上，兔子会在 $1$$1$ 号洞穴里缩成一团，睡一觉。同时，蚊子大军出动，去欺负兔子。

因为蚊子人多势众，所以它们分兵 $m\times (m-1)$$m\times (m-1)$ 路。$m$$m$ 是整个兔子洞中只和一条通道相邻的洞穴数目。任意两个这样的洞穴 $a,b$$a,b$ 之间（也就是任意两个叶子节点之间）会有两只蚊子，一只从 $a$$a$ 飞到 $b$$b$，一只从 $b$$b$ 飞到 $a$$a$。它们都沿着 $a$$a$ 到 $b$$b$ 的最短路径移动。蚊子每秒钟可以通过一条通道。所有蚊子都在 $0$$0$s 时突然出现在起点并开始移动。每只蚊子在到达终点后的一瞬间都会突然消失。有些蚊子并不会经过兔子所在的 $1$$1$ 号节点，它们起到的是恐吓作用。

又一次满脸是包地醒来后，兔子忍无可忍了，于是它找到 lrd，让 lrd 去打蚊子……lrd 不知所措，于是去某宝搞了一个灭蚊器……这个灭蚊器被放在 $1$$1$ 号节点。每个时刻，它都会工作一次，把和灭蚊器距离小于等于 $d$$d$ 范围内的蚊子全部杀死。（$d=0$$d=0$ 时只能控制 $1$$1$ 号点一个位置）

遗憾的是，兔子洞尚未通电，兔子只能用爱发电。 因此，每个时刻灭蚊器只有 $\frac{p}{q}$$\frac{p}{q}$ 的概率能够正常工作。如果不能正常工作，那么蚊子将不受到任何影响。

灭蚊器无法影响出现之前和消失之后的蚊子。但在蚊子出现在起点和消失在终点的 那个时刻，如果灭蚊器正常工作且蚊子在作用范围内，这只蚊子仍会被杀死。

兔子对 lrd 的诚意表示怀疑……于是它让 lrd 算出灭蚊器在一晚上期望能杀死多少蚊子。lrd 当然会算了，但是他想考考你。因为兔子讨厌小数，你需要输出这个期望值模 ${10}^9+7$$10^9+7$ 后的结果。即：表示为分子乘分母的逆元（对 ${10}^9+7$$10^9+7$ 取模）。 (如果你算错了，就会被 lrd 拿去喂兔子，啊呜~~)

格式

输入

第一行一个整数 $n$$n$，表示兔子洞中洞穴的个数。洞穴编号为 $1$$1$ 到 $n$$n$ 的整数。 接下来 $n-1$$n-1$ 行，每行两个整数 $u,v$$u,v$，表示 $u$$u$ 和 $v$$v$ 两个洞穴之间有一条通道。 接下来一行三个整数 $d,p,q$$d,p,q$，表示灭蚊器的作用范围是 $d$$d$，每个时刻工作的概率是 $\frac{p}{q}$$\frac{p}{q}$。

输出

一行一个整数，你的答案。

样例

输入

xxxxxxxxxx
3
1 2
1 3
1 1 2

输出

xxxxxxxxxx
750000007

范围

对于所有测试点：

$m<n\le 5000000,0\le d\le n,1\le p\le q\le {10}^9+7$$m<n\le 5000000,0\le d\le n,1\le p\le q\le 10^9+7$

本文参考了 这篇题解 的思路，有不少补充。本文的代码与那篇题解的代码有不少相似之处，有不少细节改动。

解析

树形 DP 以及树上路径的好题。这个题目的部分分很有帮助价值。

先考虑 $d=0$$d=0$ 的情况，即只有根节点被灭蚊器控制。记 $cn{t}_x$$cnt_x$ 表示以 $x$$x$ 为根的子树的叶节点数量。令

$so{n}_i$$son_i$ 表示 $i$$i$ 的子节点的集合。答案就是

相当于，把根作为 LCA 折点，对于每一棵子树，都贡献了这棵子树叶子个数与非这棵子树叶子个数的乘积，相当于乘法原理的匹配。至于蚊子双向活动的问题，$i$$i$ 刷过一遍，每个叶子会在 $(sum-cn{t}_i)$$(sum-cnt_i)$ 中刷到，也会在 $cn{t}_i$$cnt_i$ 中刷到。乘上灭蚊器消杀概率即可。

再考虑满分做法。记录动态规划数组 $f$$f$，$f_i$$f_i$ 表示所有蚊子在以 $i$$i$ 为根的子树里存活期望。同样的，令 $w$$w$ 为灭蚊器消杀概率：

以 $u$$u$ 为根的子树的贡献是：

还有一些细节。比如，题目中的分数取模，相当于乘上分母的逆元。灭蚊器消杀概率为 $\frac{p}{q}$$\frac{p}{q}$，留蚊子活路的概率是

可以全开 long long。

代码

​x
// 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;
}