rt，只过了树为链的代码，其他mle

#include<bits/stdc++.h>
#define maxn 1000006
#define inf 0x3f3f3f3f
#define lc ch[u][0]
#define rc ch[u][1]
int n,m,rt[maxn],head[maxn],a[maxn],cnt,val[maxn];
struct edge{int nxt,v;}e[maxn<<1];
inline int read()
{
	int x = 0,f = 1;char ch = getchar();
	while(ch<'0'||ch>'9')f = ch == '-'?-f:f,ch = getchar();
	while(ch>='0'&&ch<='9')x = (x<<3)+(x<<1)+ch-'0',ch = getchar();
	return x*f; 
}
inline void write(int x)
{
	if(x<0)putchar('-'),x = -x;
	static char sta[35];int top = 0;
	do{sta[top++] = x%10+'0',x/=10;}while(x);
	while(top)putchar(sta[--top]);
	putchar('\n');
}
namespace bit
{
	int c[maxn];
	inline void insert(int x,int v){while(x<=n)c[x]+=v,x+=-x&x;}
	inline int query(int x){int ret = 0;while(x)ret+=c[x],x^=-x&x;return ret;}
}
namespace tr
{
	const int S = (1979810*233)+19;
	int cnt,ch[maxn<<1][2],val[maxn<<1],size[maxn<<1],key[maxn<<1],s = 1,sta[maxn<<1],top;
	inline void maintain(int u){size[u] = size[lc]+size[rc]+1;}
	inline int getrand(){return s*=S;}
	inline int newnode(){return top?sta[--top]:++cnt;}
	inline void rorate(int&u,bool k)
	{
		int t = ch[u][k];
		ch[u][k] = ch[t][!k],ch[t][!k] = u;
		maintain(u),maintain(t),u = t;
	}
	inline void insert(int&u,int v)
	{
		if(!u)
		{
			key[u = newnode()] = getrand();
			val[u] = v,size[u] = 1;
			return;
		}
		if(v<val[u])insert(lc,v),key[u]>key[lc]?rorate(u,0):(++size[u],void());
		else insert(rc,v),key[u]>key[rc]?rorate(u,1):(++size[u],void());
	}
	inline void erase(int&u,int v)
	{
		if(!u)return;
		if(val[u] == v)
		{
			if(!lc||!rc)return sta[top++] = u,u = lc|rc,void();
			if(key[lc]<key[rc])rorate(u,0),erase(rc,v);
			else rorate(u,1),erase(lc,v);
		}
		else if(v<val[u])erase(lc,v);
		else erase(rc,v);
		--size[u];
	}
	inline int kth(int u,int k)
	{
		if(!k)return inf;
		if(k<=size[lc])return kth(lc,k);
		else if(!(k-=size[lc]+1))return val[u];
		else return kth(rc,k);
	}
}
namespace sp
{
	int hson[maxn],size[maxn],dfn[maxn],fa[maxn],top[maxn],cnt,s[10];
	void dfs1(int u)
	{
		size[u] = 1;
		for(int i = head[u],v;v = e[i].v,i;i = e[i].nxt)
			if(v!=fa[u])
			{
				fa[v] = u,dfs1(v),size[u]+=size[v];
				if(size[v]>size[hson[u]])hson[u] = v;
			}
	}
	void dfs2(int u,int tp)
	{
		dfn[u] = ++cnt,top[u] = tp;
		if(hson[u])dfs2(hson[u],tp);
		else return;
		for(int i = head[u],v;v = e[i].v,i;i = e[i].nxt)
			if(v!=hson[u]&&v!=fa[u])dfs2(v,v),tr::insert(rt[u],a[v]);
	}
	inline void tpmodify(int u,int v){tr::erase(rt[u],val[u]),val[u]+=v,tr::insert(rt[u],val[u]);}
	inline void modify(int u,int v,int k)
	{
		int tp;
		while(top[u]!=top[v])
		{
			if(dfn[u]>dfn[v])
			{
				tp = top[u];
				tpmodify(fa[tp],k);
				bit::insert(dfn[tp],k),bit::insert(dfn[u]+1,-k);
				u = fa[tp];
			}
			else
			{
				tp = top[v];
				tpmodify(fa[tp],k);
				bit::insert(dfn[tp],k),bit::insert(dfn[v]+1,-k);
				u = fa[tp];
			}
		}
		if(dfn[u]>dfn[v])std::swap(u,v);
		if(u == top[u]&&u!=1)tpmodify(u,k);
		bit::insert(dfn[u],k),bit::insert(dfn[v]+1,-k);
	}
	inline int query(int u,int k)
	{
		cnt = 0;
		s[++cnt] = bit::query(dfn[u])+a[u];
		if(k<=tr::size[rt[u]])s[++cnt] = tr::kth(rt[u],k);
		if(k>1&&k-1<=tr::size[rt[u]])s[++cnt] = tr::kth(rt[u],k-1);
		if(k>2&&k-2<=tr::size[rt[u]])s[++cnt] = tr::kth(rt[u],k-2);
		if(k>3&&k-3<=tr::size[rt[u]])s[++cnt] = tr::kth(rt[u],k-3);
		if(fa[u])s[++cnt] = bit::query(dfn[fa[u]])+a[fa[u]];
		if(hson[u])s[++cnt] = bit::query(dfn[hson[u]])+a[hson[u]];
//		for(int i = 1;i<=cnt;++i)printf("%d ",s[i]);putchar('\n');
		std::sort(s+1,s+1+cnt);
		if(k<=3)return s[k];
		else return s[4];
	}
}
int main()
{
	n = read(),m = read();
	for(int i = 1;i<=n;++i)val[i] = a[i] = read();
	for(int i = 1,u,v;i<n;++i)
	{
		u = read(),v = read();
		e[++cnt] = {head[u],v},head[u] = cnt;
		e[++cnt] = {head[v],u},head[v] = cnt;
	}
	sp::dfs1(1),sp::dfs2(1,1);
//	for(int i = 1;i<=n;++i)printf("%d ",sp::top[i]);putchar('\n');
	for(int i = 1,opt,x,y,z;i<=m;++i)
	{
		opt = read();
		if(opt == 1)
		{
			x = read(),y = read(),z = read();
			sp::modify(x,y,z);
		}
		else
		{
			x = read(),y = read();
			write(sp::query(x,y));
		}
	}
	return 0;
}