Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 200010

struct edge

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b)

{

	e[++edgenum] = (edge){b,lin[a]};lin[a] = edgenum;

	e[++edgenum] = (edge){a,lin[b]};lin[b] = edgenum;

	return;

}

int fa[MAXN],dep[MAXN],son[MAXN],top[MAXN],siz[MAXN];

void dfs1(int k,int depth)

{

	dep[k] = depth;

	siz[k] = 1;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k])

		{

			fa[e[i].to] = k;

			dfs1(e[i].to,depth + 1);

			siz[k] += siz[e[i].to];

			if(son[k] == 0 || siz[e[i].to] > siz[son[k]])

			{

				son[k] = e[i].to;

			}

		}

	}

	return;

}

int dfn[MAXN],rnk[MAXN];

void dfs2(int k,int tp)

{

	top[k] = tp;dfn[++dfn[0]] = k;rnk[k] = dfn[0];

	if(son[k] == 0)return;

	dfs2(son[k],tp);

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(e[i].to != fa[k] && e[i].to != son[k])

		{

			dfs2(e[i].to,e[i].to);

		}

	}

	return;

}

int LCA(int a,int b)

{

	while(top[a] != top[b])

	{

		if(dep[top[a]] < dep[top[b]])swap(a,b);

		a = fa[top[a]];

	}

	return (dep[a] < dep[b] ? a : b);

}

struct query

{

	int type,a,b,v;

	int id;

}q[MAXN],ql[MAXN],qr[MAXN];

bool cmp_id(query a,query b){return a.id < b.id;}

int x[MAXN],tot = 0;

int lowbit(int x){return x & (-x);}

int c[MAXN];

void addv(int p,int x){if(p == 0)return;for(int i = p;i <= n;i += lowbit(i))c[i] += x;return;}

int query(int p){int res = 0;for(int i = p;i >= 1;i -= lowbit(i))res += c[i];return res;}

void change(int a,int b,int v)

{

	int lca = LCA(a,b);

	addv(rnk[a],v);addv(rnk[b],v);

	addv(rnk[lca],-v);addv(rnk[fa[lca]],-v);

	return;

}

int calc(int k)

{

	return query(rnk[k] + siz[k] - 1) - query(rnk[k] - 1);

}

void solve(int l,int r,int L,int R)

{

	if(L == R)

	{

		for(int i = l;i <= r;++i)

		{

			if(q[i].type == 0)q[i].b = x[L];

		}

		return;

	}

	int mid = ((L + R + 1) >> 1);

	int totl = 0,totr = 0;

	int cnt = 0;

	for(int i = l;i <= r;++i)

	{

		if(q[i].type != 0)

		{

			if(q[i].v >= mid)

			{

				qr[++totr] = q[i];

				change(q[i].a,q[i].b,q[i].type);

				cnt += q[i].type;

			}

			else ql[++totl] = q[i];

		}

		else

		{

			if(cnt - calc(q[i].a) > 0)qr[++totr] = q[i];

			else ql[++totl] = q[i];

		}

	}

	for(int i = 1;i <= totr;++i)

		if(qr[i].type != 0)

			change(qr[i].a,qr[i].b,-qr[i].type);

	int cur = l;

	for(int i = 1;i <= totl;++i)q[cur++] = ql[i];

	for(int i = 1;i <= totr;++i)q[cur++] = qr[i];

	solve(l,l + totl - 1,L,mid - 1);

	solve(l + totl,r,mid,R);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs1(1,1);dfs2(1,1);

	int opt,v;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d",&opt);

		if(opt == 0)

		{

			scanf("%d%d%d",&a,&b,&v);

			q[i].a = a;q[i].b = b;q[i].v = v;q[i].type = 1;

			x[++tot] = v;

		}

		if(opt == 1)

		{

			scanf("%d",&v);

			q[i].a = q[v].a;q[i].b = q[v].b;q[i].v = q[v].v;q[i].type = -1;

		}

		if(opt == 2)

		{

			scanf("%d",&q[i].a);

			q[i].type = 0;

		}

		q[i].id = i;

	}

	sort(x + 1,x + 1 + tot);

	tot = unique(x + 1,x + 1 + tot) - x - 1;

	for(int i = 1;i <= m;++i)

	{

		if(q[i].type != 0)q[i].v = lower_bound(x + 1,x + 1 + tot,q[i].v) - x;

	}

	x[0] = -1;

	solve(1,m,0,tot);

	sort(q + 1,q + 1 + m,cmp_id);

	for(int i = 1;i <= m;++i)if(q[i].type == 0)printf("%d\n",q[i].b);

	return 0;

}