解题报告

这题在现在看来好像不是很难啊……把每对蚊子分开考虑，那么就是考虑每个节点作为LCA时的贡献，而每个节点作为LCA时又可以拆成两半处理，这样问题就简化得比较好处理了。

一个叶子到达某个祖先没被干掉的概率是 $1-(1-{p\over q})^k$ ，其中 $k$ 是到达这个祖先需要经过的被灭蚊器覆盖的节点数，如果带着前面的 $1$ 合并时会比较奇怪，所以我们可以最后加上 $m(m-1)$ ，而只计算 $(1-{p\over q})^k$ 就行了。

先计算出 $f_i$ 表示 $i$ 子树中叶子到 $i$ 的期望，这个树形DP一下很好计算。再来考虑两条链的合并：$x$ 为LCA时，他的儿子对 $(u,v)$ 产生的贡献就是 $f_uf_v{p\over q}$ （有没有 $p\over q$ 取决于 $x$ 的深度），这可以在DFS的时候记一下前缀和解决。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=5000000,MOD=1e9+7;

int n,D,P,Q,m,ans,dep[maxn+5],f[maxn+5];
int E,lnk[maxn+5],son[(maxn<<1)+5],nxt[(maxn<<1)+5];

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return (l==r&&(r=(l=buf)+fread(buf,1,100000,stdin)),l==r)?EOF:*l++;
}
inline int readi(int &x){
    int tot;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline int Pow(int w,int b) {int s=1;for (;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
void DP(int x,int pre=0,bool lf=true){
    for (int j=(dep[x]=dep[pre]+1,lnk[x]);j;j=nxt[j])
        if (son[j]!=pre){
            if (lf=false,DP(son[j],x),dep[x]<=D) AMOD(ans,(LL)2*f[x]*f[son[j]]%MOD*P%MOD);
            else AMOD(ans,(LL)2*f[x]*f[son[j]]%MOD);AMOD(f[x],f[son[j]]);
        }if (lf) f[x]=1,m++;if (dep[x]<=D) f[x]=(LL)f[x]*P%MOD;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1,x,y;i<n;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    scanf("%d%d%d",&D,&P,&Q);D++;P=(LL)(MOD-P)*Pow(Q,MOD-2)%MOD;AMOD(P,1);
    DP(1);AMOD(ans,MOD-(LL)m*(m-1)%MOD);printf("%d\n",(MOD-ans)%MOD);return 0;
}