按照*Miracle*的话来说，网上又多了一篇n^3暴力的题解
可能是因为很多猫题虽然很好，但是写正解性价比比较低？
直接做不可做，转化为统计贡献：$O(n)$枚举每个权值，直接统计第k大大于等于这个权值的联通块个数的和— —这样每个权值x恰会贡献x次。
将所有大于等于当前权值的点点权赋为1，其余点点权赋为零，然后就是$O(n^2)$树形背包：设$dp[i][j]$表示以i为根的子树里选出(新)点权和为j的联通块，且联通块必须包含i自身的方案数。
一些小小的卡常：unsigned int，减法取模，不够k个结束(这真的算卡常吗=。=)
正解需要生成函数知识，用整体DP的思想来做，线段树合并+拉格朗日插值
我们优化上面这个树形背包，考虑$f[i][j]$表示在以i为根的子树里选出点权和大于等于j的联通块数的生成函数，$g[i][j]$表示以i为根的子树所有点nde的$f[nde][j]$的和
f的转移是需要卷积的，g转移只需要加法，需要优化$f$的转移。先把f转成点值表达，这样就可以直接乘法了，最后再拉格朗日插值把多项式插出来。
转移是f的第二维对应位置相乘，然后用整体DP解决
上面四行都是我口胡的
// luogu-judger-enable-o2
#include<cstdio>
#include<cctype>
#include<cstring>
#include<algorithm>
#define uint unsigned int
using namespace std;
const int N=;
const uint mod=;
int n,k,w,t1,t2,cnt,tot;
int p[N],noww[*N],goal[*N];
int val[N],pro[N],siz[N],sze[N];
uint ans,dp[N][N];
void Read(int &x)
{
x=; char ch=getchar();
while(!isdigit(ch))
ch=getchar();
while(isdigit(ch))
x=(x<<)+(x<<)+(ch^),ch=getchar();
}
void Add(uint &x,uint y)
{
x+=y;
if(x>=mod) x-=mod;
}
void Link(int f,int t)
{
noww[++cnt]=p[f];
goal[cnt]=t,p[f]=cnt;
noww[++cnt]=p[t];
goal[cnt]=f,p[t]=cnt;
}
void DFS(int nde,int fth)
{
register int i,j,h,g;
for(i=;i<=sze[nde];i++) dp[nde][i]=;
dp[nde][pro[nde]]=,siz[nde]=pro[nde];
for(i=p[nde];i;i=noww[i])
if(goal[i]!=fth)
{
g=goal[i],DFS(g,nde);
for(j=siz[nde];~j;j--)
for(h=siz[g];~h;h--)
Add(dp[nde][j+h],dp[nde][j]*dp[g][h]%mod);
siz[nde]=siz[nde]+siz[g];
}
for(i=k;i<=siz[nde];i++) Add(ans,dp[nde][i]);
}
int main()
{
register int i,j;
Read(n),Read(k),Read(w);
for(i=;i<=n;i++) Read(val[i]);
for(i=;i<n;i++) Read(t1),Read(t2),Link(t1,t2);
for(i=;i<=w;tot=,i++)
{
for(j=;j<=n;j++) pro[j]=val[j]>=i,tot+=pro[j];
if(tot<k) printf("%u",ans),exit(); DFS(,),swap(siz,sze);
}
printf("%u",ans);
return ;
}