Description
Mr.董已经成长为一个地区的领袖，真是妙啊。董所在的地区由n个小区域构成，这些小区域构成了一棵树，每个小
区域都有一个重要程度，一个连通块的重要程度为其包含的小区域重要程度之和。现在董想进行一些调查，由于1
号区域是领袖重地，他问你包含1号的重要程度前k小的连通块重要程度分别是多少。如果连通块数不足k则全部输
出。
Input
第一行两个整数n和k。
第二行n个整数表示每个区域的重要程度。
接下来n-1行每行两个整数表示一条边。
Output
输出k行每行一个整数，第i行表示包含1号的重要程度第i小的连通块的重要程度。
如果连通块数不足k个，则不必输出k行，只要全部输出即可。具体可见样例。
100%的数据n,k<=100000，区域的重要程度的绝对值小于1,000,000,000。
只需要一个维护可重集合的数据结构，支持可持久化地合并，对一个集合中所有数加，最后能查询一次前k小，就可以按类似通常树形依赖背包的处理方法求解。
这里使用可持久化多叉堆实现，其中用可持久化左偏树维护多叉堆每个点的多个孩子。
对于合并操作直接把 堆顶元素大的堆 作为 堆顶元素小的堆 的 孩子，插进维护孩子的左偏树上，因此保证了每颗左偏树大小在O(n)，而不是直接合并的O(2)
对于加法可以直接打标记实现
最后求前k小只需把这个堆当成一棵普通的树，跑一次dijkstra
总时间复杂度O(nlogn)，常数很大
#include<bits/stdc++.h>
typedef long long i64;
const int N=1e5+;
struct node;
node*cpy(node*);
node*new_node();
struct node{
node*lc,*rc,*mc;
i64 v,a;
int h;
node*add(i64 x);
node*dn();
void up();
}*mem,*mp,*nil;
node*node::add(i64 x){
if(this==nil)return this;
node*w=new_node();
*w=(node){lc,rc,mc,v+x,a+x,h};
return w;
}
node*node::dn(){
if(this==nil)return this;
node*w=cpy(this);
if(a){
w->lc=lc->add(a);
w->rc=rc->add(a);
w->mc=mc->add(a);
w->a=;
}
return w;
}
void node::up(){
if(lc->h<rc->h)std::swap(lc,rc);
h=rc->h+;
}
node*cpy(node*w){
node*u=new_node();
*u=*w;
return u;
}
node*new_node(){
if(mem==mp)mem=new node[N],mp=mem+N;
return --mp;
}
node*mg(node*a,node*b){
if(a==nil)return b;
if(b==nil)return a;
if(a->v>b->v)std::swap(a,b);
a=a->dn();
a->rc=mg(a->rc,b);
a->up();
return a;
}
node*heap_mg(node*a,node*b){
if(a->v>b->v)std::swap(a,b);
a=a->dn();
a->mc=mg(a->mc,b->dn());
return a;
}
std::vector<int>e[N];
int n,k,v0[N];
node*f[N];
void dfs(int w,int pa){
f[w]=f[w]->add(v0[w]);
for(int i=;i<e[w].size();++i){
int u=e[w][i];
if(u==pa)continue;
f[u]=f[w];
dfs(u,w);
f[w]=heap_mg(f[w],f[u]);
}
}
char buf[N*],*ptr=buf-,ob[N*],*op=ob;
int _(){
int x=,f=,c=*++ptr;
while(c<)c=='-'?f=-:,c=*++ptr;
while(c>)x=x*+c-,c=*++ptr;
return x*f;
}
void pr(i64 x){
if(x<)x=-x,*op++='-';
int ss[],sp=;
do ss[++sp]=x%;while(x/=);
while(sp)*op++=ss[sp--]+;
*op++=;
}
struct cmp{bool operator()(node*a,node*b){return a->v>b->v;}};
std::priority_queue<node*,std::vector<node*>,cmp>q;
void push(node*w){
if(w!=nil)q.push(w);
}
int main(){
fread(buf,,sizeof(buf),stdin);
nil=new_node();
*nil=(node){nil,nil,,,-};
n=_(),k=_();
for(int i=;i<=n;++i)v0[i]=_();
for(int i=,a,b;i<n;++i){
a=_(),b=_();
e[a].push_back(b);
e[b].push_back(a);
}
*(f[]=new_node())=(node){nil,nil,nil,,,};
dfs(,);
push(f[]);
while(q.size()&&k){
--k;
node*w=q.top();q.pop();
w=w->dn();
pr(w->v);
push(w->lc);
push(w->rc);
push(w->mc);
}
fwrite(ob,,op-ob,stdout);
return ;
}