1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 100005

  4 #define L (k<<1)

  5 #define R (L+1)

  6 #define mid (l+r>>1)

  7 #define s(p) ch[k][p]

  8 struct ji{

  9     int nex,to;

 10 }edge[N<<1];

 11 int E,n,m,p,x,y,head[N],a[N],fa[N],sh[N],top[N],ma[N],id[N];

 12 int V,ro[N<<2],sz[N*50],sum[N*50],ra[N*50],v[N*50],ch[N*50][2];

 13 void add_edge(int x,int y){

 14     edge[E].nex=head[x];

 15     edge[E].to=y;

 16     head[x]=E++;

 17 }

 18 void up(int k){

 19     sz[k]=sz[s(0)]+sz[s(1)]+sum[k];

 20 }

 21 void rotate(int &k,int x,int p){

 22     s(p)=ch[x][p^1];

 23     ch[x][p^1]=k;

 24     up(k);

 25     up(k=x);

 26 }

 27 void add(int &k,int x){

 28     if (!k){

 29         v[k=++V]=x;

 30         ra[k]=rand();

 31         sz[k]=0;

 32     }

 33     sz[k]++;

 34     if (v[k]==x){

 35         sum[k]++;

 36         return;

 37     }

 38     bool p=(v[k]<x);

 39     add(s(p),x);

 40     if (ra[k]>ra[s(p)])rotate(k,s(p),p);

 41 }

 42 void del(int &k,int x){

 43     sz[k]--;

 44     if (v[k]==x){

 45         if (--sum[k])return;

 46         sum[k]++;

 47         if (s(0)*s(1)==0)k=s(0)+s(1);

 48         else{

 49             bool p=(ra[s(0)]>ra[s(1)]);

 50             rotate(k,s(p),p);

 51             del(k,x);

 52         }

 53         return;

 54     }

 55     del(s(v[k]<x),x);

 56 }

 57 int query(int k,int x){

 58     if (!k)return 0;

 59     if (v[k]==x)return sum[k]+sz[s(1)];

 60     bool p=(v[k]<x);

 61     return query(s(p),x)+(p^1)*(sum[k]+sz[s(1)]);

 62 }

 63 void update(int k,int l,int r,int x,int y,int z){

 64     if (y!=-1)del(ro[k],y);

 65     add(ro[k],z);

 66     if (l==r)return;

 67     if (x<=mid)update(L,l,mid,x,y,z);

 68     else update(R,mid+1,r,x,y,z);

 69 }

 70 int query(int k,int l,int r,int x,int y,int z){

 71     if ((l>y)||(x>r))return 0;

 72     if ((x<=l)&&(r<=y))return query(ro[k],z);

 73     return query(L,l,mid,x,y,z)+query(R,mid+1,r,x,y,z);

 74 }

 75 void dfs(int k,int f,int s){

 76     fa[k]=f;

 77     sh[k]=s;

 78     sz[k]=1;

 79     for(int i=head[k];i!=-1;i=edge[i].nex)

 80         if (edge[i].to!=f){

 81             dfs(edge[i].to,k,s+1);

 82             sz[k]+=sz[edge[i].to];

 83             if (sz[ma[k]]<sz[edge[i].to])ma[k]=edge[i].to;

 84         }

 85 }

 86 void dfs2(int k,int t){

 87     top[k]=t;

 88     id[k]=++x;

 89     update(1,1,n,x,-1,a[k]);

 90     if (ma[k])dfs2(ma[k],t);

 91     for(int i=head[k];i!=-1;i=edge[i].nex)

 92         if ((edge[i].to!=fa[k])&&(edge[i].to!=ma[k]))dfs2(edge[i].to,edge[i].to);

 93 }

 94 int query(int x,int y,int z){

 95     int ans=0;

 96     while (top[x]!=top[y]){

 97         if (sh[top[x]]<sh[top[y]])swap(x,y);

 98         ans+=query(1,1,n,id[top[x]],id[x],z);

 99         x=fa[top[x]];

100     }

101     if (id[x]>id[y])swap(x,y);

102     return ans+query(1,1,n,id[x],id[y],z);

103 }

104 int find(){

105     int l=0,r=100000000;

106     while (l<r){

107         int m=(l+r+1>>1);

108         if (query(x,y,m)>=p)l=m;

109         else r=m-1;

110     }

111     return l;

112 }

113 int main(){

114     srand(time(0));

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

116     for(int i=1;i<=n;i++)scanf("%d",&a[i]);

117     memset(head,-1,sizeof(head));

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

119         scanf("%d%d",&x,&y);

120         add_edge(x,y);

121         add_edge(y,x);

122     }

123     dfs(1,0,0);

124     x=0;

125     dfs2(1,1);

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

127         scanf("%d%d%d",&p,&x,&y);

128         if (!p){

129             update(1,1,n,id[x],a[x],y);

130             a[x]=y;

131             continue;

132         }

133         if (query(x,y,0)<p)printf("invalid request!\n");

134         else printf("%d\n",find());

135     }

136 }