#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long LL;
const int MAXN=80000+1000;
const int INF = numeric_limits<int>::max();
const LL LL_INF= numeric_limits<LL>::max();
class Treap {
public:
struct node {
node *ch[2];
int v,p,sz;
node(int _v,node *_n){ v=_v; ch[0]=ch[1]=_n; p=rand(); sz=1; }
void update(){sz=ch[0]->sz+ch[1]->sz+1;}
void fixch(node *left,node *right){ch[0]=left;ch[1]=right;}
};
node *root,*null;
Treap(){
null=new node(0,0);
null->fixch(null,null); null->sz=0;
root=null;
}
void rotate(node *&t,bool d){
node *_t=t->ch[d];
t->ch[d]=_t->ch[!d];
_t->ch[!d]=t;
t->update();
_t->update();
t=_t;
}
void __insert(node *&t,int val){
if(t==null){
t=new node(val,null);
return ;
}
bool d=(t->v < val);
__insert(t->ch[d],val);
if(t->ch[d]->p < t->p)rotate(t,d);
t->update();
}
void __del(node *&t,int val){
if(t==null)return ;
if(t->v==val){
bool d=t->ch[1]->p < t->ch[0]->p;
if(t->ch[d]==null){
node *tmp=t;
t=t->ch[!d];
delete tmp;
return ;
}
rotate(t,d);
__del(t->ch[!d],val);
}
else {
bool d=(t->v < val);
__del(t->ch[d],val);
}
t->update();
}
int __rank(node *t,int val){
if(t==null)return 0;
if(t->v < val)return __rank(t->ch[1],val);
return t->ch[1]->sz+1+__rank(t->ch[0],val);
}
void __clean(node *&t){
if(t==null)return ;
if(t->ch[0]!=null)__clean(t->ch[0]);
if(t->ch[1]!=null)__clean(t->ch[1]);
delete t;
t=null;
}
void insert(int val){ __insert(root,val); }
void del(int val){ __del(root,val); }
int rank(int val){ return __rank(root,val);}
void clean(){ __clean(root); }
~Treap(){ clean(); delete null; }
};
struct Edge {
int to,next;
Edge(){}
Edge(int _to,int _next):to(_to),next(_next){}
}e[MAXN<<1];
int head[MAXN],tot;
void AddEdge(int u,int v){
e[tot]=Edge(v,head[u]);
head[u]=tot++;
e[tot]=Edge(u,head[v]);
head[v]=tot++;
}
int dep[MAXN],fa[MAXN],son[MAXN],sz[MAXN];
int top[MAXN],tid[MAXN],ranked[MAXN],tim;
void init(){
memset(head,-1,sizeof(head));
tim=tot=0;
}
void dfs1(int u,int father,int d){
fa[u]=father;dep[u]=d;son[u]=-1;sz[u]=1;
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(fa[u]!=v){
dfs1(v,u,d+1);
sz[u]+=sz[v];
if(son[u]==-1||sz[v]>sz[son[u]])son[u]=v;
}
}
}
void dfs2(int u,int tp){
top[u]=tp;tid[u]=++tim;ranked[tid[u]]=u;
if(son[u]==-1)return ;
dfs2(son[u],tp);
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(v!=son[u]&&v!=fa[u]) dfs2(v,v);
}
}
Treap treap[MAXN<<2];
int A[MAXN];
#define lson L,mid,rt<<1
#define rson mid+1,R,rt<<1|1
void build(int L,int R,int rt){
treap[rt].clean();
for(int i=L;i<=R;i++){
treap[rt].insert(A[ranked[i]]);
}
if(L==R)return ;
int mid=(L+R)>>1;
build(lson);build(rson);
}
int query(int L,int R,int rt,int l,int r,int v){
if(l<=L&&R<=r){
return treap[rt].rank(v);
}
int mid=(L+R)>>1,ans=0;
if(l<=mid)ans+=query(lson,l,r,v);
if(r>mid)ans+=query(rson,l,r,v);
return ans;
}
void update(int L,int R,int rt,int pos,int pre,int now){
treap[rt].del(pre);
treap[rt].insert(now);
if(L==R)return ;
int mid=(L+R)>>1;
if(pos<=mid)update(lson,pos,pre,now);
else update(rson,pos,pre,now);
}
int n,q;
int queryx(int x,int y,int v){
int ans=0;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans+=query(1,n,1,tid[top[x]],tid[x],v);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans+=query(1,n,1,tid[x],tid[y],v);
return ans;
}
void updatex(int pos,int v){
update(1,n,1,tid[pos],A[pos],v);
A[pos]=v;
}
int main()
{
while(~scanf("%d%d",&n,&q)){
init();
for(int i=1;i<=n;i++)scanf("%d",&A[i]);
for(int i=0,x,y;i<n-1;i++){
scanf("%d%d",&x,&y);
AddEdge(x,y);
}
dfs1(1,0,0);
dfs2(1,1);
build(1,n,1);
for(int i=0,x,y,k;i<q;i++){
scanf("%d%d%d",&k,&x,&y);
if(k){
int l=0,r=1e+9,ans=-1;
while(l<=r){
int mid=(l+r)>>1;
int tmp1=queryx(x,y,mid);
if(tmp1<k){
ans=mid;
r=mid-1;
}
else l=mid+1;
}
if(ans-1>=0) printf("%d\n",ans-1);
else puts("invalid request!");
}
else updatex(x,y);
}
}
return 0;
}
|
