树链剖分,对每个叶子用multiset记录前K大士兵,其余节点通过从儿子归并维护前K大士兵。过于模板。
#include<set>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ls (x<<1)
#define rs (ls|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
using namespace std; const int N=;
int n,m,u,v,op,x,y,Q,K,cnt,tim,dfn[N],son[N],sz[N],dep[N],fa[N],top[N],h[N],to[N<<],nxt[N<<];
struct P{ int x,k; }p[N];
struct Se{
int tot,a[];
Se(){ tot=; memset(a,,sizeof(a)); }
Se(const Se &b){ tot=b.tot; memcpy(a,b.a,sizeof(a)); }
}T[N<<];
multiset<int>S[N<<];
void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs(int x){
sz[x]=; dep[x]=dep[fa[x]]+;
For(i,x) if ((k=to[i])!=fa[x]){
fa[k]=x; dfs(k); sz[x]+=sz[k];
if (sz[k]>sz[son[x]]) son[x]=k;
}
} void dfs2(int x,int tp){
dfn[x]=++tim; top[x]=tp;
if (son[x]) dfs2(son[x],tp);
For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]) dfs2(k,k);
} Se merge(Se a,Se b){
Se res;
for (int i=,j=; i<=a.tot || j<=b.tot; ){
if ((i<=a.tot) && (j>b.tot || b.a[j]<a.a[i])) res.a[++res.tot]=a.a[i++]; else res.a[++res.tot]=b.a[j++];
if (res.tot==K) break;
}
return res;
} void mdf(int x,int L,int R,int pos,int k,int op){
if (L==R){
if (!op) S[x].erase(S[x].find(k)); else S[x].insert(k);
T[x].tot=; multiset<int>::iterator it=S[x].end();
while (){
if (it==S[x].begin()) break; it--;
T[x].a[++T[x].tot]=*it;
if (T[x].tot==K) break;
}
return;
}
int mid=(L+R)>>;
if (pos<=mid) mdf(lson,pos,k,op); else mdf(rson,pos,k,op);
T[x]=merge(T[ls],T[rs]);
} Se que(int x,int L,int R,int l,int r){
if (L==l && r==R) return T[x];
int mid=(L+R)>>;
if (r<=mid) return que(lson,l,r);
else if (l>mid) return que(rson,l,r);
else return merge(que(lson,l,mid),que(rson,mid+,r));
} void solve(int x,int y){
Se res;
for (; top[x]!=top[y]; x=fa[top[x]]){
if (dep[top[x]]<dep[top[y]]) swap(x,y);
res=merge(res,que(,,n,dfn[top[x]],dfn[x]));
}
if (dep[x]<dep[y]) swap(x,y);
res=merge(res,que(,,n,dfn[y],dfn[x]));
if (!res.tot) puts("-1");
else{ rep(i,,res.tot) printf("%d ",res.a[i]); puts(""); }
} int main(){
freopen("bzoj4336.in","r",stdin);
freopen("bzoj4336.out","w",stdout);
scanf("%d",&n);
rep(i,,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(); dfs2(,);
scanf("%d",&m);
rep(i,,m) scanf("%d%d",&p[i].k,&p[i].x);
scanf("%d%d",&Q,&K);
rep(i,,m) mdf(,,n,dfn[p[i].x],p[i].k,);
while (Q--){
scanf("%d%d%d",&op,&x,&y);
if (op==) solve(x,y);
if (op==) mdf(,,n,dfn[p[x].x],p[x].k,),p[x].x=y,mdf(,,n,dfn[p[x].x],p[x].k,);
if (op==) mdf(,,n,dfn[p[x].x],p[x].k,),p[x].k=y,mdf(,,n,dfn[p[x].x],p[x].k,);
}
return ;
}