1 #include<iostream>  2 #include<cstdio>  3 #include<algorithm>  4 #include<vector>  5 #include<cstdlib>  6 #include<cmath>  7 #include<cstring>  8 #include<queue>  9 using namespace std; 10 #define maxn 400100 11 #define llg int 12 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 13 llg n,m,tail,deep[maxn],top[maxn],size[maxn],son[maxn],dad[maxn],id[maxn],dfsn,T,type; 14 vector<llg>a[maxn]; 15  16 struct node 17 { 18     priority_queue<llg>q1,q2; 19      20     void push1(llg x){ q1.push(x);} 21     void push2(llg x){ q2.push(x);} 22  23     llg top() 24     { 25         llg anss=-1; 26         while (!q2.empty() && (q2.top()==q1.top())) q1.pop(),q2.pop(); 27         if (!q1.empty()) anss=q1.top(); 28         return anss; 29     } 30 }val[maxn*4]; 31  32 struct data 33 { 34     llg l,r; 35 }dl[maxn]; 36  37 struct data_ 38 { 39     llg x,y,z; 40 }ask[maxn]; 41  42 bool cmp(const data&a,const data&b) {return a.l<b.l;} 43  44 void init() 45 { 46     llg x,y; 47     cin>>n>>m; 48     for (llg i=1;i<n;i++) 49     { 50         scanf("%d%d",&x,&y); 51         a[x].push_back(y),a[y].push_back(x); 52     }     53 } 54  55 void dfs_1(llg x,llg fa) 56 { 57     size[x]=1; 58     llg w=a[x].size(),v; 59     for (llg i=0;i<w;i++) 60     { 61         v=a[x][i]; 62         if (v==fa) continue; 63         deep[v]=deep[x]+1; 64         dfs_1(v,x); 65         dad[v]=x; size[x]+=size[v];   66         if (size[v]>size[son[x]]) son[x]=v; 67     } 68 } 69  70 void dfs_2(llg x,llg fa) 71 { 72     id[x]=++dfsn; 73     if (son[x]) {top[son[x]]=top[x]; dfs_2(son[x],x);} 74     llg w=a[x].size(),v; 75     for (llg i=0;i<w;i++) 76     { 77         v=a[x][i]; 78         if (v==fa || v==son[x]) continue; 79         top[v]=v; dfs_2(v,x); 80     } 81 } 82  83 void add(llg o,llg l,llg r,llg L,llg R,llg V) 84 { 85     if (l>=L && r<=R) 86     { 87         if (T) val[o].push1(V); 88         else val[o].push2(V); 89         return ; 90     } 91     llg lc=o<<1,rc=o<<1|1,mid=(l+r)>>1; 92     if (L<=mid) add(lc,l,mid,L,R,V); 93     if (R>mid) add(rc,mid+1,r,L,R,V); 94 } 95  96 void solve(llg x,llg y,llg V) 97 { 98     llg f1=top[x],f2=top[y]; 99     tail=0;100     while (f1!=f2)101     {102         if (deep[f1]<deep[f2]) swap(x,y),swap(f1,f2);103         dl[++tail].l=id[f1]; dl[tail].r=id[x];104         x=dad[f1]; f1=top[x];105     }106     if (deep[x]<deep[y]) swap(x,y);107     dl[++tail].l=id[y],dl[tail].r=id[x];108     sort(dl+1,dl+tail+1,cmp);109     llg l=0,r,last=0;110     for (llg i=1;i<=tail;i++)111     {112         l=last+1; r=dl[i].l-1;113         if (l<=r) add(1,1,n,l,r,V);114         last=dl[i].r;115     }116     l=last+1; r=n;117     if (l<=r) add(1,1,n,l,r,V);118 }119 120 llg maxl_(llg o,llg l,llg r,llg wz)121 {122     llg ans=val[o].top();123     if (l==r) return ans;124     llg mid=(l+r)>>1,lc=o<<1,rc=o<<1|1;125     if (wz<=mid) ans=max(ans,maxl_(lc,l,mid,wz));126     if (wz>mid) ans=max(ans,maxl_(rc,mid+1,r,wz));127     return ans;128 }129 130 int main()131 {132     yyj("a");133     init();134     dfs_1(1,-1);135     top[1]=1;136     dfs_2(1,-1);137     for (llg o=1;o<=m;o++)138     {139         scanf("%d",&type);140         if (type==0)141         {142             scanf("%d%d%d",&ask[o].x,&ask[o].y,&ask[o].z);143             T=1;144             solve(ask[o].x,ask[o].y,ask[o].z);145         }146         if (type==1)147         {148             llg x;149             scanf("%d",&x);150             T=0;151             solve(ask[x].x,ask[x].y,ask[x].z);152         }153         if (type==2)154         {155             llg x;156             scanf("%d",&x);157             printf("%d\n",maxl_(1,1,n,id[x]));158         }159     }160     return 0;161 }