研究半天题解啊。。。
全网几乎唯一的官方做法的题解：链接
别的都是暴力。。。。
要是n=3333暴力就完了。
一、问题转化
每个联通块第k大的数，直观统计的话，会枚举每个点作为第k大，看看有多少个连通块。但是这样要点分治。而且在d[x]相同的时候可能算重
所以必须以连通块来统计
考虑在连通块的最浅的点统计
但是第k大不一定是这个点
考虑一个套路：用许多次分别统计，最后实际上凑出答案的想法。
而且本题权值范围和n同阶。
外层枚举每一个i∈[1,w]，DP找到所有“包含大于等于w的点有至少k个”的连通块的个数
所有的i的总和就是答案。每个连通块恰好统计了第k大的数权值的次数
这样就可以在连通块最浅点统计辣。
二、DP
DP就很显然了
外层枚举i∈[1,w]，dp[x][j]以x为根的子树，选择了大于等于i的有j个的方案数
卷积型背包转移。注意每个儿子还可以不选。
最后答案是每次i的每个x的dp[x][k~n]的和的和
看上去似乎优化到头了。（这时候暴力就可以AC了）
但是，
下面开始神仙思路了：
“DP数组是死的，但是套上高级算法就活了”
既然是一个卷积，不妨考虑用生成函数的思想，再用一些多项式的科技和高级数据结构等等来搞搞事情。
现在dp是一个生成函数，首先有：
（注意，可能x有的时候是树的节点编号，有的时候可能是生成函数里的x变量）
$dp[x]=\Pi (dp[son]+1)*Z$
$Z=x^{[d[x]>=i]}$
是一个多项式，当d[x]>=i的时候，Z是x，否则是0，象征x这个点自己是否能够作为>=i的点。
看上去更差劲了，，先接着往下看
三、整体DP
一个强大的思想，是把许多次DP（比如这里要做w次）一起做，叫做整体DP
一般用线段树合并维护，当前点x的线段树的叶子节点下标y的位置的权值，是第y次dp到x这里的权值
考虑把一次影响贡献到所有的DP中。或者说，我们这次外层枚举x，内层枚举每一个DP
线段树合并的时候，更新一些DP值。
但是，，，
这个题每个x的DP是一个数组，不是一个值，，，对应位置卷积，，线段树合并无能为力。。。
生成函数的卷积太麻烦，我们把它变成点值
最外层（主函数）枚举i=1~N+1，象征要求所有的DP的生成函数在x=i时候的点值的和。（注意是和，因为其实是对于每个x统计连通块的个数）
现在，外层枚举到i，dfs到点cur的线段树中下标为y的叶子的f值的意义是：在第y次DP时候，dp[cur]这个生成函数在x=i时候的点值
现在每个位置不是多项式，而是一个值辣。
而我们还要知道所有位置的点值之和，便于统计最后答案
线段树每个叶子再来一个g：外层枚举到i，dfs到点cur的线段树中下标为y的叶子的g值的意义是：在第y次DP时候，整个子树dp[]这个生成函数在x=i时候的点值之和
四、线段树合并
外层枚举i=1~N+1
先考虑要做什么：
1.x的每个位置先赋值为1
2.dfs下去，合并
3.乘上自己的贡献。前[1,d[x]]乘上i,后[d[x]+1,n]乘上1
4.把自己的f贡献到自己的g
4.有一个：$dp[x]=\Pi (dp[son]+1)*Z$
$dp[son]+1$所以干脆把全局f回溯前全局+1
我们需要用线段树维护对于每个子树的对于每个叶子的变换（维护一会说
（最后在rt统计信息不用pushup，只有pushdown）
线段树合并时候对应位置点值相乘（因为真实的dp[x]生成函数最多n项）
对应位置相乘没法做，但是位置同时乘上一个数可以做。由于区间操作，所以在全区间都是同一个“变换”的时候，直接给x树位置乘上变换即可。
变换是什么？
需要支持：
1.维护f，维护g
2.给f+1，给f乘一个数
3.f加到g上去。
设置一个变换（应该是一个群）：(a,b,c,d)
定义乘法：$(a1,b1,c1,d1) × (a2,b2,c2,d2)=(a1×a2,a2×b1+b2,c1+c2*a1,c2*b1+d2+d1)$
定义单位元：
$(1,0,0,0)$
推一推发现，这个变换有结合律。可以支持标记合并。
我们把f放在b位置，g放在d位置，就可以维护了。（暴力讨论维护一定也可以，但是绝对不如这个变换的设计好写）
详见代码。
五、插值部分
我们得到的是点值。ans[i]表示最终的生成函数（把所有点的W次求的生成函数加起来）在x=i时候的点值。
用拉格朗日插值还原，见另一篇博客。[学习笔记]拉格朗日插值
六、实现细节：
1.64123相乘爆int，用unsigned int
2.每次可以垃圾回收，所以线段树合并用&，使得y的儿子直接变掉（看代码
代码：
#include<bits/stdc++.h>
#define il inline
#define reg register int
#define ui unsigned int
#define mid ((l+r)>>1)
#define numb (ch^'0')
using namespace std;
typedef long long ll;
il void rd(int &x){
char ch;bool fl=false;
while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true);
for(x=numb;isdigit(ch=getchar());x=x*+numb);
(fl==true)&&(x=-x);
}
namespace Miracle{
const int N=;
const int mod=;
int n,k,w;
int d[N];
struct node{
int nxt,to;
}e[*N];
int hd[N],cnt;
void add(int x,int y){
e[++cnt].nxt=hd[x];
e[cnt].to=y;
hd[x]=cnt;
}
struct data{
int a,b,c,d;
data(){}
data(int aa,int bb,int cc,int dd){
a=aa;b=bb;c=cc;d=dd;
}
data friend operator *(data A,data B){
return data((ui)A.a*B.a%mod,((ui)A.b*B.a+B.b)%mod,((ui)B.c*A.a+A.c)%mod,((ui)B.c*A.b+A.d+B.d)%mod);
}
void clear(){
a=,b=,c=,d=;
}
};
struct tr{
int ls,rs;
data val;
tr(){val.a=;val.b=;val.c=;val.d=;ls=rs=;}
void clear(){val.a=;val.b=;val.c=;val.d=;ls=rs=;}
}t[*N];
int sta[*N],top,tot;
int nc(){
return top?sta[top--]:++tot;
}
int rt[N];
int ans[N];//dian zhi
int b[N];//true xishu
int f[N];
int c[N];
int inv[mod+];
void del(int &x){
if(!x) return;
if(t[x].ls) del(t[x].ls);
if(t[x].rs) del(t[x].rs);
sta[++top]=x;
t[x].clear();
x=;
}
void pushdown(int x){
if(!t[x].ls) t[x].ls=nc();
if(!t[x].rs) t[x].rs=nc();
t[t[x].ls].val=t[t[x].ls].val*t[x].val;
t[t[x].rs].val=t[t[x].rs].val*t[x].val;
t[x].val.clear();
}
int query(int x,int l,int r){
if(l==r) return t[x].val.d;
pushdown(x);
int ret=query(t[x].ls,l,mid);
ret=(ret+query(t[x].rs,mid+,r))%mod;
return ret;
}
void upda(int &x,int l,int r,int L,int R,data c){
if(!x) x=nc();
if(L<=l&&r<=R){
t[x].val=t[x].val*c;
return;
}
pushdown(x);
if(L<=mid) upda(t[x].ls,l,mid,L,R,c);
if(mid<R) upda(t[x].rs,mid+,r,L,R,c);
}
int merge(int &x,int &y){
//if(!x||!y) return x+y;每次都会pushdown产生儿子。所以这里不需要
if(!t[x].ls&&!t[x].rs) swap(x,y);
if(!t[y].ls&&!t[y].rs){
t[x].val=t[x].val*data(t[y].val.b,,,);
t[x].val=t[x].val*data(,,,t[y].val.d);
return x;
}
pushdown(x);pushdown(y);
t[x].ls=merge(t[x].ls,t[y].ls);
t[x].rs=merge(t[x].rs,t[y].rs);
return x;
}
void dfs(int x,int fa,int k0){
upda(rt[x],,w,,w,data(,,,));
for(reg i=hd[x];i;i=e[i].nxt){
int y=e[i].to;
if(y==fa) continue;
dfs(y,x,k0);
rt[x]=merge(rt[x],rt[y]);
del(rt[y]);
}
upda(rt[x],,w,,d[x],data(k0,,,));
upda(rt[x],,w,,w,data(,,,));
upda(rt[x],,w,,w,data(,,,));
}
void Lagelangri(){
f[]=;
for(reg i=;i<=n+;++i){
for(reg j=n+;j>=;--j){
f[j]=((ui)f[j]*(mod-i)%mod+(j?f[j-]:))%mod;
}
} for(reg i=;i<=n+;++i){
ll tmp=;
for(reg j=;j<=n+;++j){
c[j]=f[j];
if(j!=i) {
if(j<i) tmp=tmp*inv[i-j]%mod;
else tmp=tmp*(mod-inv[j-i])%mod;
}
}
c[]=f[];
tmp=tmp*ans[i]%mod;
for(reg j=;j<=n+;++j){
if(!j) c[j]=(mod-(ll)c[j]*inv[i]%mod)%mod;
else c[j]=(mod-((ll)c[j]-c[j-]+mod)*inv[i]%mod)%mod;
} for(reg j=;j<=n;++j){
b[j]=((ll)b[j]+c[j]*tmp%mod)%mod;
}
}
}
int main(){
rd(n);rd(k);rd(w);
int x,y;
for(reg i=;i<=n;++i){
rd(d[i]);
}
for(reg i=;i<n;++i){
rd(x);rd(y);add(x,y);add(y,x);
}
for(reg i=;i<=n+;++i){
dfs(,,i);
ans[i]=query(rt[],,w);
del(rt[]);
}
inv[]=;
for(reg i=;i<=n+;++i) inv[i]=(ll)(mod-mod/i)*inv[mod%i]%mod;
Lagelangri();
ll op=;
for(reg i=k;i<=n;++i){
op=(op+b[i])%mod;
}
printf("%lld",op);
return ;
} }
signed main(){
Miracle::main();
return ;
} /*
Author: *Miracle*
Date: 2019/2/19 9:45:33
*/
总结：
1.题意转化使得连通块可以直接在最浅的地方统计，模型简单，为后面套高级算法留下可能性
2.生成函数思想+点值，妈妈再也不用担心卷积太复杂！~
3.整体DP，赋值之间大同小异，所以所有DP值一起处理，
4.拉格朗日插值O(n^2)trick
神仙啊~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~