求恰好第k大的权值显然不可做，差分一下，转换成：
枚举(W)，求第k大(>=W)的方案数，发现对所有这样的(W)的方案数加起来就是答案。
这样就相当于权值(>=W)选了有1的贡献，权值(<W)选了没有贡献。
要求选的1的个数(>=k)的方案数。
显然这个可以用暴力树形依赖背包在(O(n^2))的时间解决，总复杂度(O(n^3))，据说就能跑过数据了。
考虑用整体dp的思想去解决这个问题：
设(F[i][j])表示(i)为根子树，(W=j)，得到的方案数的OGF。
注意到(F[i][j])只有(siz[i])段不同的OGF。
(F)的转移就是枚举(i)的一个子节点，然后把相同(j)对应的OGF乘起来，如果用线段树合并去实现，合并OGF时套个FFT，时间复杂度：(O(n^2~log^2n))，明显只会更慢。
考虑把(F[i][j])转换成一个(0-n)的点值序列，这样转移就是(O(n))的，最后再(O(n^2)) 拉格朗日插值得到(x^{k..n})的系数和就行了，可以把点值的操作挪到最外层以节省空间。
线段树合并没有那么简单，在这个特殊的线段树上，一个点没有子节点，说明它代表的区间的值时相同的。
假设现在(merge(i,j))，当(i,j)有一方没有子节点时，就要停下来，直接操作，才能保证复杂度。
经过讨论可以发现需要维护：
区间赋值（初始化），区间乘、区间加，区间求和
写就完了。
Code：
#include<bits/stdc++.h>
#define fo(i, x, y) for(int i = x, _b = y; i <= _b; i ++)
#define ff(i, x, y) for(int i = x, _b = y; i < _b; i ++)
#define fd(i, x, y) for(int i = x, _b = y; i >= _b; i --)
#define ll long long
#define pp printf
#define hh pp("
")
using namespace std;
const int mo = 64123;
ll ksm(ll x, ll y) {
ll s = 1;
for(; y; y /= 2, x = x * x % mo)
if(y & 1) s = s * x % mo;
return s;
}
const int N = 1705;
int n, k, w, m;
int d[N], x, y;
#define V vector<int>
#define pb push_back
#define si size()
V e[N];
void Init() {
scanf("%d %d %d", &n, &k, &w);
fo(i, 1, n) scanf("%d", &d[i]);
fo(i, 1, n - 1) {
scanf("%d %d", &x, &y);
e[x].pb(y); e[y].pb(x);
}
}
int fa[N], rt[N];
#define i0 t[i].l
#define i1 t[i].r
struct P {
ll x, y, s;
P(ll _x = 0, ll _y = 0, ll _s = 0) {
x = _x, y = _y, s = _s;
}
};
P operator * (P a, P b) {
return P(a.x * b.x % mo, (a.y * b.x + b.y) % mo, a.s);
}
struct tree {
int l, r;
P v;
} t[N * 55]; int tt;
int pl, pr;
int W;
void cl() {
fo(i, 1, n) rt[i] = 0;
fo(i, 1, tt) t[i].l = t[i].r = 0, t[i].v = P(1, 0, 0);
tt = 0;
}
void down(int i, int x, int y) {
int m = x + y >> 1;
if(i0) {
t[i0].v = t[i0].v * t[i].v;
t[i1].v = t[i1].v * t[i].v;
t[i0].v.s = (t[i0].v.s * t[i].v.x + t[i].v.y * (m - x + 1)) % mo;
t[i1].v.s = (t[i1].v.s * t[i].v.x + t[i].v.y * (y - m)) % mo;
t[i].v = P(1, 0);
} else {
t[i0 = ++ tt].v = t[i].v;
t[i1 = ++ tt].v = t[i].v;
t[i0].v.s = t[i].v.y * (m - x + 1) % mo;
t[i1].v.s = t[i].v.y * (y - m) % mo;
t[i].v = P(1, 0);
}
}
void upd(int i) {
t[i].v.s = (t[i0].v.s + t[i1].v.s) % mo;
}
void bt(int &i, int x, int y) {
if(!i) i = ++ tt;
t[i].v = P(1, 0, 0);
if(y <= pl || x > pl) {
t[i].v = P(1, y <= pl ? W : 1, 0);
t[i].v.s = t[i].v.y * (y - x + 1) % mo;
return;
}
int m = x + y >> 1;
bt(i0, x, m); bt(i1, m + 1, y);
upd(i);
}
int mer(int i, int j, int x, int y) {
if(!t[j].l) {
ll v2 = t[j].v.y + 1;
t[i].v.x = t[i].v.x * v2 % mo;
t[i].v.y = t[i].v.y * v2 % mo;
t[i].v.s = t[i].v.s * v2 % mo;
return i;
}
if(!t[i].l) {
ll v2 = t[i].v.y;
t[j].v.y ++;
t[j].v.s += y - x + 1;
t[j].v.x = t[j].v.x * v2 % mo;
t[j].v.y = t[j].v.y * v2 % mo;
t[j].v.s = t[j].v.s * v2 % mo;
return j;
}
int m = x + y >> 1;
down(i, x, y); down(j, x, y);
i0 = mer(i0, t[j].l, x, m);
i1 = mer(i1, t[j].r, m + 1, y);
upd(i);
return i;
}
ll ans[N];
void dg(int x) {
pl = pr = d[x];
bt(rt[x], 1, m);
ff(_y, 0, e[x].si) {
int y = e[x][_y];
if(y == fa[x]) continue;
fa[y] = x;
dg(y);
rt[x] = mer(rt[x], rt[y], 1, m);
}
ans[W] = (ans[W] + t[rt[x]].v.s) % mo;
}
ll f[N], g[N], h[N];
ll inv[N];
void End() {
fo(i, 0, n + 1) inv[i] = ksm(i, mo - 2);
f[0] = 1;
fo(i, 0, n) {
fd(j, i + 1, 0) f[j] = (f[j] * -i + (j ? f[j - 1] : 0)) % mo;
}
ll sum = 0;
fo(i, 0, n) {
fo(j, 0, n + 1) g[j] = f[j];
fd(j, n + 1, 1) {
h[j - 1] = g[j];
g[j - 1] = (g[j - 1] + i * g[j]) % mo;
}
ll xs = ans[i];
fo(j, 0, n) if(i != j) {
int x = i - j;
xs = xs * (x > 0 ? inv[x] : -inv[-x]) % mo;
}
fo(j, k, n) sum = (sum + xs * h[j]) % mo;
}
sum = (sum % mo + mo) % mo;
pp("%lld
", sum);
}
int main() {
Init();
m = 1666; //ggggggggggggggggggggggggggggggg
for(W = 0; W <= n; W ++) {
cl();
dg(1);
}
End();
}