Description
在一片古老的土地上，有一个繁荣的文明。
这片大地几乎被森林覆盖，有N座城坐落其中。巧合的是，这N座城由恰好N-1条双
向道路连接起来，使得任意两座城都是连通的。也就是说，这些城形成了树的结构，任意两
座城之间有且仅有一条简单路径。
在这个文明中，骑士是尤其受到尊崇的职业。任何一名骑士，都是其家族乃至家乡的荣
耀。Henry从小就渴望成为一名能守护家乡、驱逐敌人的骑士。勤奋训练许多年后，Henry
终于满18岁了。他决定离开家乡，向那些成名已久的骑士们发起挑战！
根据Henry的调查，大陆上一共有M名受封骑士，不妨编号为1到M。
第i个骑士居住在城Pi，武力值为Fi。
Henry计划进行若干次旅行，每次从某座城出发沿着唯一的简单路径前往另一座城，
同时会挑战路线上武力值最高的K个骑士（Henry的体力有限，为了提高水平，当然要挑
战最强的骑士）。如果路线上的骑士不足K人，Henry会挑战遇到的所有人。
每次旅行前，可能会有某些骑士的武力值或定居地发生变化，Henry自然会打听消息，
并对计划做出调整。
为了在每次旅行时做好充分准备，Henry希望你能帮忙在每次旅行前计算出这条路线
上他将挑战哪些对手。
Input
第一行，一个整数N，表示有N座城，编号为1~N。
接下来N-1行，每行两个整数Ui和Vi，表示城Ui和城Vi之间有一条道路相连。
第N+1行，一个整数M，表示有M个骑士。
接下来M行，每行两个整数Fi和Pi。按顺序依次表示编号为1~M的每名骑士的武
力值和居住地。
第N+M+2行，两个整数Q,K，分别表示操作次数和每次旅行挑战的骑士数目上限。
接下来Q行，每行三个整数Ti,Xi,Yi。Ti取值范围为{1,2,3}，表示操作类型。
一共有以下三种类型的操作：
Ti=1时表示一次旅行，Henry将从城Xi出发前往城市Yi；
Ti=2时表示编号为Xi的骑士的居住地搬到城Yi；
Ti=3时表示编号为Xi的骑士的武力值修正为Yi。
Output
输出若干行，依次为每个旅行的答案。
对每个Ti=1的询问，输出一行，按从大到小的顺序输出Henry在这次旅行中挑战的
所有骑士的武力值。如果路线上没有骑士，输出一行，为一个整数-1。
对每个点用multiset维护点权，树链剖分+线段树维护区间上前k大的数（降序），对于查询可以把对应的区间提取出来用堆维护一下多路归并求出前k大
单次查询时间复杂度约为O((log^2(n)+k)log(log^2(n)))，修改为O(klogn)
#include<bits/stdc++.h> const int N=40007; char buf[N*100],*ptr=buf-1; int _(){ int x=0,c=*++ptr; while(c<48)c=*++ptr; while(c>47)x=x*10+c-48,c=*++ptr; return x; } int n,m,q,k; int es[N*2],enx[N*2],e0[N],ep=2; std::multiset<int,std::greater<int> >vs[N]; int as[N],bs[N]; int fa[N],sz[N],son[N],dep[N],top[N],id[N],idr[N],idp=0; int _l,_r,*Q[N],qp; bool cmp(int*a,int*b){ return *a<*b; } void push(int*a){ Q[qp++]=a; std::push_heap(Q,Q+qp,cmp); } struct node{ node*lc,*rc,*f; int L,R; int v[21]; void init(int x){ int p=0; for(std::multiset<int>::iterator it=vs[x].begin();p<k&&it!=vs[x].end();v[p++]=*(it++)); for(;p<k;v[p++]=-1); } void up(){ int p=0,p1=0,p2=0,*v1=lc->v,*v2=rc->v; while(p<k&&p1<k&&p2<k)v[p++]=v1[p1]>v2[p2]?v1[p1++]:v2[p2++]; while(p<k&&p1<k)v[p++]=v1[p1++]; while(p<k&&p2<k)v[p++]=v2[p2++]; } void upds(){ for(node*w=f;w;w->up(),w=w->f); } void get(){ if(_l<=L&&R<=_r){ if(~v[0])push(v); return; } int M=L+R>>1; if(_l<=M)lc->get(); if(_r>M)rc->get(); } }ns[N*2],*np=ns,*rt[N],*pos[N]; node*build(int L,int R){ node*w=np++; w->L=L;w->R=R; memset(w->v,-1,sizeof(w->v)); if(L!=R){ int M=L+R>>1; (w->lc=build(L,M))->f= (w->rc=build(M+1,R))->f=w; w->up(); }else{ pos[idr[L]]=w; w->init(idr[L]); } return w; } void f1(int w,int pa){ dep[w]=dep[fa[w]=pa]+1; sz[w]=1; for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=pa){ f1(u,w); sz[w]+=sz[u]; if(sz[u]>sz[son[w]])son[w]=u; } } } void f2(int w,int tp){ top[w]=tp; idr[id[w]=++idp]=w; if(son[w])f2(son[w],tp); else rt[tp]=build(id[tp],id[w]); for(int i=e0[w];i;i=enx[i]){ int u=es[i]; if(u!=fa[w]&&u!=son[w])f2(u,u); } } int main(){ buf[fread(buf,1,sizeof(buf),stdin)]=0; n=_(); for(int i=1,a,b;i<n;++i){ a=_();b=_(); es[ep]=b;enx[ep]=e0[a];e0[a]=ep++; es[ep]=a;enx[ep]=e0[b];e0[b]=ep++; } m=_(); for(int i=1;i<=m;++i){ as[i]=_();bs[i]=_(); vs[bs[i]].insert(as[i]); } q=_();k=_(); f1(1,0);f2(1,1); for(int i=0,o,x,y;i<q;++i){ o=_();x=_();y=_(); if(o==1){ qp=0; int a=top[x],b=top[y]; while(a!=b){ if(dep[a]<dep[b])std::swap(x,y),std::swap(a,b); _l=id[a],_r=id[x],rt[a]->get(); x=fa[a];a=top[x]; } if(dep[x]>dep[y])std::swap(x,y); _l=id[x],_r=id[y],rt[top[x]]->get(); if(!qp)printf("-1"); for(int j=0;j<k&&qp;++j){ int*p=Q[0]; std::pop_heap(Q,Q+qp--,cmp); printf("%d ",*p); if(~*++p)push(p); } putchar(10); }else if(o==2){ vs[bs[x]].erase(vs[bs[x]].find(as[x])); pos[bs[x]]->init(bs[x]); pos[bs[x]]->upds(); vs[bs[x]=y].insert(as[x]); pos[bs[x]]->init(bs[x]); pos[bs[x]]->upds(); }else{ vs[bs[x]].erase(vs[bs[x]].find(as[x])); vs[bs[x]].insert(as[x]=y); pos[bs[x]]->init(bs[x]); pos[bs[x]]->upds(); } } return 0; }