bzoj4336: BJOI2015 骑士的旅行

#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;
}