根据题意,我们可以发现这是一道树形 dp。首先考虑设计状态,注意到 \(k\) 较小,那么我们可以在 dp 数组里面塞一维来维护特殊颜色点的个数。然后题目里有颜色编号的大小限制,所以第三维用 \(0/1/2\) 来分别表示当前颜色小于/等于/大于 \(k\) 的情况。那么这样的话就是用 \(f_{i,j,0/1/2}\) 表示在以 \(i\) 为根的子树内,有 \(j\) 个特殊颜色在三种情况下的答案。那么转移方程式即为:
\[f_{x,i+j,0}=\sum \limits_{y \in son_x}{f_{x,i,0} \times (f_{y,j,0}+f_{y,j,1}+f_{y,j,2})}
\]
\[f_{x,i+j,1} = \sum \limits_{y \in son_x}{f_{x,i,1} \times f_{y,j,0}}
\]
\[f_{x,i+j,2} = \sum \limits_{y \in son_x}{f_{x,i,2} \times (f_{y,j,0}+f_{y,j,2})}
\]
树形背包转移即可。
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
const int N=1e5+10;
inline int read(){
int f=1,w=0;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
w=(w<<1)+(w<<3)+(c^48);
c=getchar();
}
return f*w;
}
struct node{
int to,nex;
}e[N*2];
int head[N],tot;
void add_edge(int x,int y){
e[++tot].to=y;
e[tot].nex=head[x];
head[x]=tot;
}
int n,m;
int k,lim;
int f[N][15][3];
int siz[N];
int tmp[15][3];
void dfs(int x,int fa){
siz[x]=1;
f[x][0][0]=k-1;
f[x][1][1]=1;
f[x][0][2]=m-k;
for(int p=head[x];p;p=e[p].nex){
int y=e[p].to;
if(y==fa) continue;
dfs(y,x);
siz[x]+=siz[y];
for(int i=0;i<=min(siz[x],lim);i++){
tmp[i][0]=f[x][i][0];
f[x][i][0]=0;
tmp[i][1]=f[x][i][1];
f[x][i][1]=0;
tmp[i][2]=f[x][i][2];
f[x][i][2]=0;
}
for(int i=0;i<=min(siz[x],lim);i++){
for(int j=0;j<=min(siz[y],lim-i);j++){
(f[x][i+j][0]+=(tmp[i][0]*(((f[y][j][0]+f[y][j][1])%mod+f[y][j][2])%mod)%mod)%mod)%=mod;
(f[x][i+j][1]+=tmp[i][1]*f[y][j][0]%mod)%=mod;
(f[x][i+j][2]+=(tmp[i][2]*((f[y][j][0]+f[y][j][2])%mod)%mod)%mod)%=mod;
}
}
}
}
signed main(){
n=read();
m=read();
for(int i=1;i<n;i++){
int x,y;
x=read();
y=read();
add_edge(x,y);
add_edge(y,x);
}
k=read();
lim=read();
dfs(1,0);
int ans=0;
for(int i=0;i<=lim;i++){
(ans+=((f[1][i][0]+f[1][i][1])%mod+f[1][i][2])%mod)%=mod;
}
cout<<ans<<endl;
return 0;
}