好题，牛牛的一个套路。
先树剖一下，我们可以很简单的用树状数组维护每个点的真实值。
对于每个点只维护所有轻儿子的信息，对于每次询问的时候暴力加入当前点，重儿子以及父亲的信息，查询第 \(k\) 大，再删除信息即可。
考虑链修改的影响。因为只维护的是轻儿子的信息，那么只有链上的所有轻边会修改。
具体的，设当前轻边 \((x,y)\)，\(y\) 是父亲，先在 \(y\) 中删除原来 \(x\) 的信息，再加入当前 \(x\) 的真实信息即可。
树剖链查询的时候只会经过 \(O(\log n)\) 的轻边，用平衡树维护每个点的信息即可，直接用 pb_ds 就好了！
默认 \(n,m\) 同阶，复杂度 \(O(n \log^2 n)\)。
小细节：树剖最后链修改 \(x,y\) 跳到一条重链时，如果一端是重链头，需要对它的父亲进行修改。
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef long long ll;
const int N=1e6+3;
int n,m,a[N];
vector<int>ve[N];
struct Nod
{
int x,id;
friend bool operator <(Nod a,Nod b){return a.x!=b.x?a.x<b.x:a.id<b.id;}
};
tree<Nod,null_type,less<Nod>,rb_tree_tag,tree_order_statistics_node_update>tr[N];
struct BIT
{
int tr[N];
void Add(int x,int y){for(;x<=n;x+=x&-x)tr[x]+=y;}
int Ask(int x){int s=0;for(;x;x-=x&-x)s+=tr[x];return s;}
void Mdf(int l,int r,int d){Add(l,d);Add(r+1,-d);}
}T;
struct ShuPou
{
int sz[N],fa[N],dep[N],hson[N],tim,top[N],dfn[N],pos[N];
void Dfs1(int x)
{
sz[x]=1;dep[x]=dep[fa[x]]+1;
for(int y:ve[x])if(y!=fa[x])
{
fa[y]=x;Dfs1(y);sz[x]+=sz[y];
if(sz[hson[x]]<sz[y])hson[x]=y;
}
}
void Dfs2(int x,int tp)
{
top[x]=tp;pos[x]=++tim;dfn[tim]=x;T.Mdf(tim,tim,a[x]);
if(hson[x])Dfs2(hson[x],tp);
for(int y:ve[x])if(y!=fa[x]&&y!=hson[x])Dfs2(y,y),tr[x].insert({a[y],y});
}
void Upd(int x,int y,int z)
{
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
int tp=top[x];tr[fa[tp]].erase({a[tp],tp});
T.Mdf(pos[tp],pos[x],z);a[tp]=T.Ask(pos[tp]);
tr[fa[tp]].insert({a[tp],tp});x=fa[top[x]];
}
if(dep[x]<dep[y])swap(x,y);
if(dep[y]!=dep[top[y]]||!fa[y]){T.Mdf(pos[y],pos[x],z);return;}
tr[fa[y]].erase({a[y],y});T.Mdf(pos[y],pos[x],z);
a[y]=T.Ask(pos[y]);tr[fa[y]].insert({a[y],y});
}
}Sp;
void Add(int x,int y){if(y)tr[x].insert({T.Ask(Sp.pos[y]),y});}
void Del(int x,int y){if(y)tr[x].erase({T.Ask(Sp.pos[y]),y});}
int main()
{
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1,x,y;i<n;i++)cin>>x>>y,ve[x].push_back(y),ve[y].push_back(x);
Sp.Dfs1(1);Sp.Dfs2(1,1);
while(m--)
{
int op,x,y,z;cin>>op>>x>>y;
if(op==1){cin>>z;Sp.Upd(x,y,z);continue;}
Add(x,x);Add(x,Sp.hson[x]);Add(x,Sp.fa[x]);
cout<<tr[x].find_by_order(y-1)->x<<'\n';
Del(x,x);Del(x,Sp.hson[x]);Del(x,Sp.fa[x]);
}
}
有任何疑惑欢迎与我交流。