题意：树上单点修改，询问链上k大值。
思路：
1.DFS序+树状数组套主席树
首先按照套路，关于k大值的问题，肯定要上主席树，每个点维护一棵权值线段树记录它到根的信息。
关于询问，就是Que(u)+Que(v)-Que(LCA(u,v))-Que(father(LCA(u,v)))，线段树上二分查询第k大即可。
考虑修改，修改一个点影响到的点为它子树中的所有点，所以要用DFS序。于是这实际上是区间修改单点询问的问题，外面套一层主席树即可。
$O(n\log^2 n)$
2.二分+树链剖分+线段树套平衡树
由于是链上询问，考虑树链剖分。首先二分答案mid，然后问题转化为求mid在这条链上的排名，在树链上用线段树维护，每棵树中维护一棵平衡树，用来求排名。
$O(n\log^4 n)$理论上会超但实际上常数比较小。
第一种码力太弱码不出来，写了第二种，速度OJ上倒数（空间倒是十分优秀）。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (x<<1)
#define rs (ls|1)
#define lson ls,L,mid
#define rson rs,mid+1,R
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
#define For(i,x) for (int i=h[x],k; i; i=nxt[i])
using namespace std; const int N=,M=;
bool vis[N];
int n,Q,cnt,tot,nd,tmp,tim,ans,u,v;
int val[M],lc[M],rc[M],hp[M],sz[M],w[M];
int T[N],pos[N],b[N<<],fa[N],son[N],dep[N],top[N],root[N<<];
int h[N],to[N<<],nxt[N<<];
struct Que{ int k,a,b; }q[N]; void add(int u,int v){ to[++cnt]=v; nxt[cnt]=h[u]; h[u]=cnt; } void dfs1(int x){
sz[x]=;
For(i,x) if ((k=to[i])!=fa[x]){
fa[k]=x; dep[k]=dep[x]+; dfs1(k); sz[x]+=sz[k];
if (sz[k]>sz[son[x]]) son[x]=k;
}
} void dfs2(int x,int tp){
top[x]=tp; pos[x]=++tim;
if (son[x]) dfs2(son[x],tp);
For(i,x) if ((k=to[i])!=fa[x] && k!=son[x]) dfs2(k,k);
} int lca(int u,int v){
for (; top[u]!=top[v]; u=fa[top[u]])
if (dep[top[u]]<dep[top[v]]) swap(u,v);
return (dep[u]<dep[v]) ? u : v;
} void rrot(int &x){
int y=lc[x]; lc[x]=rc[y]; rc[y]=x;
sz[y]=sz[x]; sz[x]=sz[lc[x]]+sz[rc[x]]+w[x]; x=y;
} void lrot(int &x){
int y=rc[x]; rc[x]=lc[y]; lc[y]=x;
sz[y]=sz[x]; sz[x]=sz[lc[x]]+sz[rc[x]]+w[x]; x=y;
} void ins(int &x,int k){
if (!x) { x=++nd; sz[x]=w[x]=; hp[x]=rand(); val[x]=k; return; }
sz[x]++;
if (k==val[x]) { w[x]++; return; }
if (k<val[x]){ ins(lc[x],k); if (hp[lc[x]]<hp[x]) rrot(x); }
else{ ins(rc[x],k); if (hp[rc[x]]<hp[x]) lrot(x); }
} void del(int &x,int k){
if (val[x]==k){
if (w[x]>) { sz[x]--; w[x]--; return; }
if (!lc[x] || !rc[x]) { x=lc[x]+rc[x]; return; }
if (hp[lc[x]]<hp[rc[x]]) rrot(x),del(x,k);
else lrot(x),del(x,k);
return;
}
sz[x]--;
if (k<val[x]) del(lc[x],k); else del(rc[x],k);
} void getrank(int x,int k){
if (!x) return;
if (val[x]==k) tmp+=sz[rc[x]];
else if (k>val[x]) getrank(rc[x],k); else tmp+=sz[rc[x]]+w[x],getrank(lc[x],k);
} void mdf(int x,int L,int R,int pos,int a,int b){
if (~a) del(root[x],a); ins(root[x],b);
if (L==R) return;
int mid=(L+R)>>;
if (pos<=mid) mdf(lson,pos,a,b); else mdf(rson,pos,a,b);
} void que(int x,int L,int R,int l,int r,int k){
if (L==l && r==R){ getrank(root[x],k); return; }
int mid=(L+R)>>;
if (r<=mid) que(lson,l,r,k);
else if (l>mid) que(rson,l,r,k);
else que(lson,l,mid,k),que(rson,mid+,r,k);
} void Get(int x,int f,int k){
while (top[x]!=top[f]) que(,,n,pos[top[x]],pos[x],k),x=fa[top[x]];
que(,,n,pos[f],pos[x],k);
} void solve(int x,int y,int k){
int t=lca(x,y); ans=-;
if (dep[x]+dep[y]-dep[t]-dep[fa[t]]<k){ puts("invalid request!"); return; }
int L=,R=tot;
while (L<=R){
int mid=(L+R)>>;
tmp=; Get(x,t,mid); Get(y,t,mid);
if (T[t]>mid) tmp--;
if (tmp<k) R=mid-,ans=mid; else L=mid+;
}
printf("%d\n",b[ans]);
} int main(){
freopen("bzoj1146.in","r",stdin);
freopen("bzoj1146.out","w",stdout);
scanf("%d%d",&n,&Q);
rep(i,,n) scanf("%d",&T[i]),b[++tot]=T[i];
rep(i,,n) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dep[]=; dfs1(); dfs2(,);
rep(i,,Q){
scanf("%d%d%d",&q[i].k,&q[i].a,&q[i].b);
if (!q[i].k) b[++tot]=q[i].b;
}
sort(b+,b+tot+); tot=unique(b+,b+tot+)-b-;
rep(i,,n) T[i]=lower_bound(b+,b+tot+,T[i])-b;
rep(i,,Q) if (!q[i].k) q[i].b=lower_bound(b+,b+tot+,q[i].b)-b;
rep(i,,n) mdf(,,n,pos[i],-,T[i]);
rep(i,,Q)
if (!q[i].k) mdf(,,n,pos[q[i].a],T[q[i].a],q[i].b),T[q[i].a]=q[i].b;
else solve(q[i].a,q[i].b,q[i].k);
return ;
}