对于任意两个事件 X, Y :
E(X + Y ) = E(X) + E(Y ) 。
对于两个相互独立事件 X, Y :
E(XY ) = E(X)E(Y )
因此,对于两个相互独立事件 X, Y ,有:
E((X + Y ) j ) = ∑ j k=0 C jk E(X k ) E(Y j−k )
但是对于E(X^k)*E(Y^0)和E(X^0)*E(Y^k)要根据题目含义单独考虑。
x&&y:E(X^0)=P*1
x||y:E(X^0)=1
y依附于x：E(Y^0)=1,E(X^0)=P;
灵活考虑，不要拘泥于式子。
#include<bits/stdc++.h>#define F(i,a,b) for(rg int i=a;i<=b;++i)#define rg register#define pf(a) printf("%lld ",a)#define phn puts("")#define LL long long#define il inlineusing namespace std;#define int LLint read();#define N 200010int n,m,p,q;const int mod=1e9+7;int a[N],f[N][12],g[N][12],C[15][15];int to[N<<1],fir[N<<1],head[N<<1],cnt;il int qpow(int x,int k){int s=1;for(;k;x=x*x%mod,k>>=1)if(k&1)s=s*x%mod;return s;}il void add(int x,int y){to[++cnt]=y;fir[cnt]=head[x];head[x]=cnt;}void dfs(int x,int fa){g[x][0]=1;f[x][0]=1;g[x][1]=p*a[x]%mod;f[x][1]=p*a[x]%mod;F(i,2,m){g[x][i]=g[x][i-1]*a[x]%mod;f[x][i]=f[x][i-1]*a[x]%mod;}for(int i=head[x];i;i=fir[i]){int v=to[i];if(v==fa)continue;dfs(v,x);for(int j=m;j>=1;--j){(f[x][j]+=f[v][j])%=mod;F(k,1,j-1){(f[x][j]+=C[j][k]*g[x][k]%mod*g[v][j-k]%mod)%=mod;}//f[x][j]%=mod; }for(int j=m;j>=1;--j){(g[x][j]+=p*g[v][j])%=mod;F(k,1,j-1){(g[x][j]+=C[j][k]*g[x][k]%mod*g[v][j-k]%mod)%=mod;}//g[x][j]%=mod; }}}signed main(){C[0][0]=1;F(i,1,12){C[i][0]=1;F(j,1,i)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}n=read();m=read();p=read();q=read();p=p*qpow(q,mod-2)%mod;int x,y;F(i,1,n)a[i]=read();F(i,2,n){x=read();y=read();add(x,y);add(y,x);}dfs(1,0);printf("%lld\n",f[1][m]);}il int read(){int s=0;rg char ch;while(ch=getchar(),!isdigit(ch));for(;isdigit(ch);s=s*10+(ch^48),ch=getchar());return s;}/*g++ 1.cpp -gtime ./a.out3 2 1 21 2 41 21 3*/
View Code
