记录编号	265344	评测结果	AAAAAAAAAA
题目名称	[HNOI 2016] 网络	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	4.321 s
提交时间	2016-06-02 16:54:03	内存使用	61.22 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int maxn=500010;
int n,Q,cnt,fir[maxn],nxt[maxn<<1],to[maxn<<1];
void addedge(int a,int b){
    nxt[++cnt]=fir[a];fir[a]=cnt;to[cnt]=b;
}

struct Data{
    int ID,val;
    Data(int id=0,int V=0){
        ID=id;val=V;
    }
    bool operator <(const Data &a)const{
        return val<a.val;
    } 
};

priority_queue<Data>Mx[maxn<<2];

int dep[maxn],fa[maxn],sz[maxn],son[maxn];
bool del[maxn<<1];

void DFS(int x){
    sz[x]=1;
    for(int i=fir[x];i;i=nxt[i])
        if(to[i]!=fa[x]){
            fa[to[i]]=x;
            dep[to[i]]=dep[x]+1;
            DFS(to[i]);
            sz[x]+=sz[to[i]];
            if(sz[son[x]]<sz[to[i]])
                son[x]=to[i];
        }
}

int tot,ID[maxn],top[maxn];

void DFS(int x,int tp){
    ID[x]=++tot;top[x]=tp;
    if(son[x])DFS(son[x],tp);
    for(int i=fir[x];i;i=nxt[i])
        if(to[i]!=fa[x]&&to[i]!=son[x])
            DFS(to[i],to[i]);
}

int Query(int x,int l,int r,int g){
    while((!Mx[x].empty())&&del[Mx[x].top().ID])
        Mx[x].pop();
    if(l==r)
        return Mx[x].empty()?-1:Mx[x].top().val;    
    int mid=(l+r)>>1,ret=Mx[x].empty()?-1:Mx[x].top().val;
    if(mid>=g)return max(ret,Query(x<<1,l,mid,g));
    else return max(ret,Query(x<<1|1,mid+1,r,g));
}

struct Node{
    int l,r;
    Node(int L=0,int R=0){
        l=L;r=R;
    }
    bool operator <(const Node &a)const{
        return l<a.l;
    }
}st[maxn<<2];

void Update(int x,int l,int r,int a,int b,int id,int val){
    if(l>=a&&r<=b){
        Mx[x].push(Data(id,val));
        return;
    }
    int mid=(l+r)>>1;
    if(mid>=a)Update(x<<1,l,mid,a,b,id,val);
    if(mid<b)Update(x<<1|1,mid+1,r,a,b,id,val);
    return;
}

void Solve(int x,int y,int id,int val){
    int tp=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
            
        st[++tp]=Node(ID[top[x]],ID[x]);
        x=fa[top[x]];    
    }
    
    if(dep[x]<dep[y])swap(x,y);
    st[++tp]=Node(ID[y],ID[x]);
    
    sort(st+1,st+tp+1);
    
    int L=1;
    for(int i=1;i<=tp;i++){
        if(L<=st[i].l-1)
            Update(1,1,n,L,st[i].l-1,id,val);
        L=st[i].r+1;    
    }
    
    if(L<=n)
        Update(1,1,n,L,n,id,val);
    
    return;    
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("network_tenderRun.in","r",stdin);
    freopen("network_tenderRun.out","w",stdout);
#endif
    scanf("%d%d",&n,&Q);
    for(int i=1,a,b;i<n;i++){
        scanf("%d%d",&a,&b);
        addedge(a,b);
        addedge(b,a);
    }
        
    DFS(1);
    DFS(1,1);
        
    for(int t=1,type,a,b,v;t<=Q;t++){
        scanf("%d",&type);
        if(type==0){
            scanf("%d%d%d",&a,&b,&v);
            Solve(a,b,t,v);
        }
        else if(type==1){
            scanf("%d",&a);
            del[a]=true;
        }
        else if(type==2){
            scanf("%d",&a);
            printf("%d\n",Query(1,1,n,ID[a]));
        }
    }
    return 0;
}