分析
首先把第 $k$ 大转化掉：
$$
\begin{aligned}
&\sum_{S\subseteq U}S\text{ 的第 }k\text{ 大点权}\\
=&\sum_{i=1}^W\sum_{S\subseteq U}[S\text{ 的第 }k\text{ 大点权 }\geq i]\\
=&\sum_{i=1}^W\sum_{S\subseteq U}[(S\text{ 中点权 }\geq i\text{ 的点数 })\geq i]\\
\end{aligned}
$$
考虑一个 DP。设 $f_{i,j,k}$ 表示以 $i$ 为根的子树、权值 $\geq j$ 的点共有 $k$ 个的方案数。答案即为 $\sum_{i=1}^n\sum_{j=1}^W\sum_{p=k}^n f_{i,j,p}$。
转移是树形背包：
$$
f_{i,j,k}=\sum_{[d_i\geq j]+\sum_va_v=k}\prod_v\left(f_{v,j,a_v}+[a_v=0]\right)
$$
直接做是 $\mathcal{O}(n^2W)$ 的，大力卡可以卡过去。
既然是背包，考虑写成生成函数的形式。设 $F_{i,j}(x)=\sum_k f_{i,j,k}x^k$，转移变为
$$
F_{i,j}=x^{[d_i\geq j]}\prod_v\left(F_{v,j}+1\right)
$$
不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和，并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。
看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都是 $x^n$，所以我们可以想办法求出 $n+1$ 个点值，然后再拉格朗日插值求出系数。
点值有一个好处，就是原来的卷积变成了对应位置相乘。那么我们相当于要支持：
- 把所有 $F_{i,j}(x)$ 加上 $1$；
- 把所有 $F_{i,j}(x)$ 乘上一个数；
- 把所有 $G_{i,j}(x)$ 加上 $F_{i,j}(x)$。
使用整体 DP 的思想，对每个节点开一棵以 $j$ 为下标的线段树，维护 $F_{i,j}(x)$ 和 $G_{i,j}(x)$ 的值。具体的，我们构造一个变换 $(a,b,c,d)$，表示将 $(f,g)$ 变为 $(af+b,cf+d+g)$。手推可以知道两个变换 $(a_1,b_1,c_1,d_1)$ 和 $(a_2,b_2,c_2,d_2)$ 合并后得到 $(a_1a_2,a_2b_1+b_2,c_1+c_2a_1,c_2b_1+d_1+d_2)$，且这个合并是满足结合律的。这样子就可以求出点值，进一步得到答案了。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=1666+10;
const int mod=64123;
int qpow(int a,int b) { int c=1;
for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) c=1ll*c*a%mod;
return c;
}
int n,k,W,d[N];
vector<int> E[N];
struct alice {
int a,b,c,d;
alice(int a_=1,int b_=0,int c_=0,int d_=0): a(a_),b(b_),c(c_),d(d_) {}
};
alice operator +(alice x,alice y) {
return alice(1ll*x.a*y.a%mod,(1ll*y.a*x.b+y.b)%mod,
(x.c+1ll*y.c*x.a)%mod,(1ll*y.c*x.b+x.d+y.d)%mod);
}
bool operator !=(alice x,alice y) {
return x.a!=y.a||x.b!=y.b||x.c!=y.c||x.d!=y.d;
}
#define ls(o) t[o].lc
#define rs(o) t[o].rc
struct node {
int lc,rc; alice w;
node(int lc_=0,int rc_=0,alice w_=alice()): lc(lc_),rc(rc_),w(w_) {}
} t[N*30];
int rt[N],tot=0;
int newnode() { t[++tot]=node(); return tot; }
void pushdown(int o) {
if (!ls(o)) ls(o)=newnode();
if (!rs(o)) rs(o)=newnode();
if (t[o].w!=alice()) {
t[ls(o)].w=t[ls(o)].w+t[o].w;
t[rs(o)].w=t[rs(o)].w+t[o].w;
t[o].w=alice();
}
}
void modify(int &o,int l,int r,int ql,int qr,alice w) {
if (!o) o=newnode();
if (ql<=l&&r<=qr) { t[o].w=t[o].w+w; return; }
int mid=(l+r)>>1; pushdown(o);
if (ql<=mid) modify(ls(o),l,mid,ql,qr,w);
if (qr>mid) modify(rs(o),mid+1,r,ql,qr,w);
}
int query(int o,int l,int r,int ql,int qr) {
if (!o) return 0;
if (l==r) return t[o].w.d;
int mid=(l+r)>>1,res=0; pushdown(o);
if (ql<=mid) res=query(ls(o),l,mid,ql,qr);
if (qr>mid) res=(res+query(rs(o),mid+1,r,ql,qr))%mod;
return res;
}
int merge(int x,int y) {
if (!x||!y) return x+y;
if (!ls(x)&&!rs(x)) {
t[y].w=t[y].w+alice(t[x].w.b,0,0,0);
t[y].w=t[y].w+alice(1,0,0,t[x].w.d);
return y;
}
if (!ls(y)&&!rs(y)) {
t[x].w=t[x].w+alice(t[y].w.b,0,0,0);
t[x].w=t[x].w+alice(1,0,0,t[y].w.d);
return x;
}
pushdown(x),pushdown(y);
ls(x)=merge(ls(x),ls(y)),rs(x)=merge(rs(x),rs(y));
return x;
}
#undef ls
#undef rs
void dfs(int u,int fa,int x) {
modify(rt[u]=0,1,W,1,W,alice(0,1,0,0));
for (int v:E[u]) {
if (v==fa) continue;
dfs(v,u,x),rt[u]=merge(rt[u],rt[v]);
}
modify(rt[u],1,W,1,d[u],alice(x,0,0,0));
modify(rt[u],1,W,1,W,alice(1,0,1,0));
modify(rt[u],1,W,1,W,alice(1,1,0,0));
}
int ans[N],f[N],g[N],h[N],inv[N];
void Lagrange() {
for (int i=1;i<=n+1;++i) inv[i]=qpow(i,mod-2);
f[0]=1;
for (int i=1;i<=n+1;++i) {
for (int j=n+1;j;--j)
f[j]=(1ll*f[j]*(mod-i)+f[j-1])%mod;
f[0]=1ll*f[0]*(mod-i)%mod;
}
for (int i=1;i<=n+1;++i) {
memcpy(h,f,sizeof(h));
for (int j=0;j<=n;++j)
h[j]=1ll*(mod-inv[i])*h[j]%mod,h[j+1]=(h[j+1]-h[j]+mod)%mod;
int c=1;
for (int j=1;j<=n+1;++j) {
if (i==j) continue;
if (j<i) c=1ll*c*inv[i-j]%mod;
else c=1ll*c*(mod-inv[j-i])%mod;
}
c=1ll*c*ans[i]%mod;
for (int j=0;j<=n+1;++j) g[j]=(g[j]+1ll*h[j]*c)%mod;
}
}
int main() {
n=read(),k=read(),W=read();
for (int i=1;i<=n;++i) d[i]=read();
for (int i=1;i<n;++i) {
int u=read(),v=read();
E[u].emplace_back(v),E[v].emplace_back(u);
}
for (int i=1;i<=n+1;++i) {
tot=0,dfs(1,0,i);
ans[i]=query(rt[1],1,W,1,W);
}
Lagrange(); int ans=0;
for (int i=k;i<=n;++i) ans=(ans+g[i])%mod;
printf("%d\n",ans);
return 0;
}