分析：
听说正解是FFT+线段树合并，然而我并不会...
我们来思考其他的方法。
我们要求的是连通块第k大的和
对于某一个连通块，对答案的贡献=val(Rank.K)
我们不好直接算出每个连通块的Rank.K是多少
但我们可以枚举一个limit for 1->w ，Σ(val(Rank.K)>=lim的连通块的个数)就等于答案
为什么呢，因为这样一个连通块就被统计了val(Rank.K)次。
剩下的进行树形DP，设dp[i][j]为以i为根的子树，选出j个权值>=limit的点的方案数。
那么最后统计答案的时候便是Σ(dp[i][j])(K<=j<=size(i))
复杂度N^3其实是不对的，但是卡一卡常数还是过得去的
代码：
#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define RG register int #define rep(i,a,b) for(RG i=a;i<=b;++i) #define per(i,a,b) for(RG i=a;i>=b;--i) #define ll long long #define inf (1<<29) #define maxn 2000 #define add(x,y) e[++cnt].v=y,e[cnt].next=head[x],head[x]=cnt using namespace std; int n,m,cnt,w; int ss[maxn],isn[maxn],head[maxn]; ll lim,ans; ll val[maxn],dp[maxn][maxn],sz[maxn]; //dp[i][j] 在以i为根的子树，选择了j个权值大于等于lim的点的方案数 const ll mo=64123; struct E{ int v,next; }e[maxn<<1]; inline int read() { int x=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} return x*f; } inline int MO(int x,int v){x+=v;return x>=mo?x-mo:x;} void dfs(int u,int fa) { sz[u]=(val[u]>=lim)?1:0; dp[u][sz[u]]=1; for(int i=head[u];i;i=e[i].next) { int v=e[i].v; if(v==fa) continue; dfs(v,u); per(ii,sz[u],0) if(dp[u][ii]) per(j,sz[v],0) if(dp[v][j])dp[u][ii+j]=MO(dp[u][ii+j],(dp[u][ii]*dp[v][j])%mo); sz[u]+=sz[v]; } rep(i,m,sz[u]) ans=MO(ans,dp[u][i]); } int main() { n=read(),m=read(),w=read(); rep(i,1,n) val[i]=read(),ss[val[i]]++; for(RG i=1,u,v;i<n;i++) u=read(),v=read(),add(u,v),add(v,u); per(i,w,1) ss[i]+=ss[i+1]; rep(i,1,w) { if(ss[i]<m) break; memset(dp,0,sizeof(dp));lim=i; dfs(1,0); } cout<<ans; return 0; }