#include<stdio.h>
#include<algorithm>
#include<vector>
#define pb push_back
#define maxn 100005
#define maxait 1<<20 //segment tree size
using namespace std;
int n,m,nrp,nrl,sol;
int ait[maxait];
int v[maxn],lev[maxn],nr[maxn],liniar[maxn];
int pfather[maxn],path[maxn],lpos[maxn],start[maxn];
vector <int> l[maxn],p[maxn];
//n-number of nodes; m-number of queries; nrp-number of paths;
//nrl-number of elements of liniar[i]
//ait[i]-segment tree
//v[i]-value of node i;
//lev[i]-level of node i; nr[i]-number of nodes in the subtree of node i;
//liniar[i]-paths concatenated
//pfather[i]-the node that represents the father of path i;
//path[i]-path of node i;
//lpos[i]-position of node i in liniar[]
//start[i]-start position of path i in vector liniar[]
//l[i]-list of nodes adjacent to node i
//p[i]-ith path
void read()
{
int x,y;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
l[x].pb(y); l[y].pb(x); //bidirectional edge between nodes x and y
}
}
void dfs(int k,int level,int father) //k-current node,level-clevel,father-cfather
{
int nrc=0,ind; //nrc-maximum nodes int the subtree of a son and ind=son index
lev[k]=level; nr[k]=1;
for(unsigned int i=0;i<l[k].size();i++) // for all adjacent nodes to k
if(!lev[l[k][i]]) //not visited
{
dfs(l[k][i],level+1,k); //next node
nr[k]+=nr[l[k][i]]; //we add the number of nodes in the subtree of a son to the father total
if(nr[l[k][i]]>nrc) nrc=nr[l[k][i]],ind=l[k][i];
}
//if leaf then make a new path that contains only k
if(l[k].size()==1 && k!=1) p[++nrp].pb(k),path[k]=nrp,pfather[nrp]=father;
else p[path[ind]].pb(k),path[k]=path[ind],pfather[path[ind]]=father;
//else add the node to the heavyest path
}
void build(int k,int left,int right)
{
if(left==right) {ait[k]=v[liniar[left]]; return;}
int mid=(left+right)>>1;
build(2*k,left,mid);
build(2*k+1,mid+1,right);
ait[k]=max(ait[2*k],ait[2*k+1]);
}
void make_paths()
{
for(int k=1;k<=nrp;k++)
{
start[k]=nrl+1;
reverse(p[k].begin(),p[k].end()); //reverse the path order
for(unsigned int i=0;i<p[k].size();i++)
liniar[++nrl]=p[k][i],lpos[p[k][i]]=nrl; //add paths to liniar[]
//maintain positions and pathstart
}
build(1,1,n); //build the segment tree on liniar[]
}
void update(int k,int left,int right,int posc)
{
if(left==right) {ait[k]=v[liniar[left]]; return;}
int mid=(left+right)>>1;
if(posc<=mid) update(2*k,left,mid,posc);
else update(2*k+1,mid+1,right,posc);
ait[k]=max(ait[2*k],ait[2*k+1]);
}
void query(int k,int left,int right,int x,int y)
{
if( x<=left && right<=y ) {sol=max(sol,ait[k]); return;}
int mid=(left+right)>>1;
if(x<=mid) query(2*k,left,mid,x,y);
if(y>mid) query(2*k+1,mid+1,right,x,y);
}
void solve()
{
int type,x,y;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&type,&x,&y);
if(!type)
{
v[x]=y;
update(1,1,n,lpos[x]); //change the value of node x to y
continue;
}
sol=0;
while(path[x]!=path[y])
{
if(lev[pfather[path[x]]]<lev[pfather[path[y]]]) swap(x,y);
query(1,1,n,start[path[x]],lpos[x]);
x=pfather[path[x]];
}
if(lpos[x]>lpos[y]) swap(x,y);
query(1,1,n,lpos[x],lpos[y]); //get the query answer in sol
printf("%d\n",sol);
}
}
int main()
{
freopen("heavypath.in","r",stdin);
freopen("heavypath.out","w",stdout);
read();
dfs(1,1,0); //get the paths
make_paths(); //concatenate the paths
solve(); //solve the queries
fclose(stdin);
fclose(stdout);
return 0;
}
I2luY2x1ZGU8c3RkaW8uaD4KI2luY2x1ZGU8YWxnb3JpdGhtPgojaW5jbHVkZTx2ZWN0b3I+CiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbWF4biAxMDAwMDUKI2RlZmluZSBtYXhhaXQgMTw8MjAgICAvL3NlZ21lbnQgdHJlZSBzaXplCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CiAKaW50IG4sbSxucnAsbnJsLHNvbDsgIAppbnQgYWl0W21heGFpdF07CmludCB2W21heG5dLGxldlttYXhuXSxuclttYXhuXSxsaW5pYXJbbWF4bl07CmludCBwZmF0aGVyW21heG5dLHBhdGhbbWF4bl0sbHBvc1ttYXhuXSxzdGFydFttYXhuXTsKdmVjdG9yIDxpbnQ+IGxbbWF4bl0scFttYXhuXTsKIAogLy9uLW51bWJlciBvZiBub2RlczsgbS1udW1iZXIgb2YgcXVlcmllczsgbnJwLW51bWJlciBvZiBwYXRoczsKIC8vbnJsLW51bWJlciBvZiBlbGVtZW50cyBvZiBsaW5pYXJbaV0KIC8vYWl0W2ldLXNlZ21lbnQgdHJlZQogLy92W2ldLXZhbHVlIG9mIG5vZGUgaTsKIC8vbGV2W2ldLWxldmVsIG9mIG5vZGUgaTsgbnJbaV0tbnVtYmVyIG9mIG5vZGVzIGluIHRoZSBzdWJ0cmVlIG9mIG5vZGUgaTsgCiAvL2xpbmlhcltpXS1wYXRocyBjb25jYXRlbmF0ZWQKIC8vcGZhdGhlcltpXS10aGUgbm9kZSB0aGF0IHJlcHJlc2VudHMgdGhlIGZhdGhlciBvZiBwYXRoIGk7CiAvL3BhdGhbaV0tcGF0aCBvZiBub2RlIGk7CiAvL2xwb3NbaV0tcG9zaXRpb24gb2Ygbm9kZSBpIGluIGxpbmlhcltdCiAvL3N0YXJ0W2ldLXN0YXJ0IHBvc2l0aW9uIG9mIHBhdGggaSBpbiB2ZWN0b3IgbGluaWFyW10KIC8vbFtpXS1saXN0IG9mIG5vZGVzIGFkamFjZW50IHRvIG5vZGUgaQogLy9wW2ldLWl0aCBwYXRoCiAKdm9pZCByZWFkKCkKewogICAgaW50IHgseTsKICAgIHNjYW5mKCIlZCVkIiwmbiwmbSk7CiAgICBmb3IoaW50IGk9MTtpPD1uO2krKykgc2NhbmYoIiVkIiwmdltpXSk7CiAgICBmb3IoaW50IGk9MTtpPG47aSsrKQogICAgewogICAgICAgIHNjYW5mKCIlZCVkIiwmeCwmeSk7CiAgICAgICAgbFt4XS5wYih5KTsgbFt5XS5wYih4KTsgICAvL2JpZGlyZWN0aW9uYWwgZWRnZSBiZXR3ZWVuIG5vZGVzIHggYW5kIHkKICAgIH0KfQogCnZvaWQgZGZzKGludCBrLGludCBsZXZlbCxpbnQgZmF0aGVyKSAvL2stY3VycmVudCBub2RlLGxldmVsLWNsZXZlbCxmYXRoZXItY2ZhdGhlcgp7CiAgICBpbnQgbnJjPTAsaW5kOyAgICAgICAgICAgICAgICAvL25yYy1tYXhpbXVtIG5vZGVzIGludCB0aGUgc3VidHJlZSBvZiBhIHNvbiBhbmQgaW5kPXNvbiBpbmRleAogICAgbGV2W2tdPWxldmVsOyBucltrXT0xOyAKICAgIGZvcih1bnNpZ25lZCBpbnQgaT0wO2k8bFtrXS5zaXplKCk7aSsrKSAvLyBmb3IgYWxsIGFkamFjZW50IG5vZGVzIHRvIGsKICAgICBpZighbGV2W2xba11baV1dKSAvL25vdCB2aXNpdGVkCiAgICAgewogICAgICAgICBkZnMobFtrXVtpXSxsZXZlbCsxLGspOyAvL25leHQgbm9kZQogICAgICAgICBucltrXSs9bnJbbFtrXVtpXV07IC8vd2UgYWRkIHRoZSBudW1iZXIgb2Ygbm9kZXMgaW4gdGhlIHN1YnRyZWUgb2YgYSBzb24gdG8gdGhlIGZhdGhlciB0b3RhbAogICAgICAgICBpZihucltsW2tdW2ldXT5ucmMpIG5yYz1ucltsW2tdW2ldXSxpbmQ9bFtrXVtpXTsgCiAgICAgfQogCiAJLy9pZiBsZWFmIHRoZW4gbWFrZSBhIG5ldyBwYXRoIHRoYXQgY29udGFpbnMgb25seSBrCiAgICBpZihsW2tdLnNpemUoKT09MSAmJiBrIT0xKSBwWysrbnJwXS5wYihrKSxwYXRoW2tdPW5ycCxwZmF0aGVyW25ycF09ZmF0aGVyOwogICAgZWxzZSBwW3BhdGhbaW5kXV0ucGIoaykscGF0aFtrXT1wYXRoW2luZF0scGZhdGhlcltwYXRoW2luZF1dPWZhdGhlcjsKICAgIC8vZWxzZSBhZGQgdGhlIG5vZGUgdG8gdGhlIGhlYXZ5ZXN0IHBhdGggCn0KIAp2b2lkIGJ1aWxkKGludCBrLGludCBsZWZ0LGludCByaWdodCkKewogICAgaWYobGVmdD09cmlnaHQpIHthaXRba109dltsaW5pYXJbbGVmdF1dOyByZXR1cm47fQogICAgaW50IG1pZD0obGVmdCtyaWdodCk+PjE7CiAgICBidWlsZCgyKmssbGVmdCxtaWQpOwogICAgYnVpbGQoMiprKzEsbWlkKzEscmlnaHQpOwogICAgYWl0W2tdPW1heChhaXRbMiprXSxhaXRbMiprKzFdKTsKfQogCnZvaWQgbWFrZV9wYXRocygpCnsKICAgIGZvcihpbnQgaz0xO2s8PW5ycDtrKyspCiAgICB7CiAgICAgICAgc3RhcnRba109bnJsKzE7CiAgICAgICAgcmV2ZXJzZShwW2tdLmJlZ2luKCkscFtrXS5lbmQoKSk7IC8vcmV2ZXJzZSB0aGUgcGF0aCBvcmRlcgogICAgICAgIGZvcih1bnNpZ25lZCBpbnQgaT0wO2k8cFtrXS5zaXplKCk7aSsrKQogICAgICAgICAgbGluaWFyWysrbnJsXT1wW2tdW2ldLGxwb3NbcFtrXVtpXV09bnJsOyAvL2FkZCBwYXRocyB0byBsaW5pYXJbXQogICAgICAgICAgLy9tYWludGFpbiBwb3NpdGlvbnMgYW5kIHBhdGhzdGFydAogICAgfQogICAgYnVpbGQoMSwxLG4pOyAvL2J1aWxkIHRoZSBzZWdtZW50IHRyZWUgb24gbGluaWFyW10KfQogCnZvaWQgdXBkYXRlKGludCBrLGludCBsZWZ0LGludCByaWdodCxpbnQgcG9zYykKewogICAgaWYobGVmdD09cmlnaHQpIHthaXRba109dltsaW5pYXJbbGVmdF1dOyByZXR1cm47fQogICAgaW50IG1pZD0obGVmdCtyaWdodCk+PjE7CiAgICBpZihwb3NjPD1taWQpIHVwZGF0ZSgyKmssbGVmdCxtaWQscG9zYyk7CiAgICBlbHNlIHVwZGF0ZSgyKmsrMSxtaWQrMSxyaWdodCxwb3NjKTsKIAogICAgYWl0W2tdPW1heChhaXRbMiprXSxhaXRbMiprKzFdKTsKfQogCnZvaWQgcXVlcnkoaW50IGssaW50IGxlZnQsaW50IHJpZ2h0LGludCB4LGludCB5KQp7CiAgICBpZiggeDw9bGVmdCAmJiByaWdodDw9eSApIHtzb2w9bWF4KHNvbCxhaXRba10pOyByZXR1cm47fQogICAgaW50IG1pZD0obGVmdCtyaWdodCk+PjE7CiAgICBpZih4PD1taWQpIHF1ZXJ5KDIqayxsZWZ0LG1pZCx4LHkpOwogICAgaWYoeT5taWQpIHF1ZXJ5KDIqaysxLG1pZCsxLHJpZ2h0LHgseSk7Cn0KIAp2b2lkIHNvbHZlKCkKewogICAgaW50IHR5cGUseCx5OwogICAgZm9yKGludCBpPTE7aTw9bTtpKyspCiAgICB7CiAgICAgICAgc2NhbmYoIiVkJWQlZCIsJnR5cGUsJngsJnkpOwogICAgICAgIGlmKCF0eXBlKQogICAgICAgIHsKICAgICAgICAgICAgdlt4XT15OwogICAgICAgICAgICB1cGRhdGUoMSwxLG4sbHBvc1t4XSk7IC8vY2hhbmdlIHRoZSB2YWx1ZSBvZiBub2RlIHggdG8geQogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CiAgICAgICAgc29sPTA7CiAgICAgICAgd2hpbGUocGF0aFt4XSE9cGF0aFt5XSkKICAgICAgICB7CiAgICAgICAgICAgIGlmKGxldltwZmF0aGVyW3BhdGhbeF1dXTxsZXZbcGZhdGhlcltwYXRoW3ldXV0pIHN3YXAoeCx5KTsKICAgICAgICAgICAgcXVlcnkoMSwxLG4sc3RhcnRbcGF0aFt4XV0sbHBvc1t4XSk7CiAgICAgICAgICAgIHg9cGZhdGhlcltwYXRoW3hdXTsKICAgICAgICB9CiAgICAgICAgaWYobHBvc1t4XT5scG9zW3ldKSBzd2FwKHgseSk7CiAgICAgICAgcXVlcnkoMSwxLG4sbHBvc1t4XSxscG9zW3ldKTsgLy9nZXQgdGhlIHF1ZXJ5IGFuc3dlciBpbiBzb2wKICAgICAgICBwcmludGYoIiVkXG4iLHNvbCk7CiAgICB9Cn0KIAppbnQgbWFpbigpCnsKICAgIGZyZW9wZW4oImhlYXZ5cGF0aC5pbiIsInIiLHN0ZGluKTsKICAgIGZyZW9wZW4oImhlYXZ5cGF0aC5vdXQiLCJ3IixzdGRvdXQpOwogCiAgICByZWFkKCk7IAogICAgZGZzKDEsMSwwKTsgICAgLy9nZXQgdGhlIHBhdGhzCiAgICBtYWtlX3BhdGhzKCk7ICAvL2NvbmNhdGVuYXRlIHRoZSBwYXRocyAKICAgIHNvbHZlKCk7ICAgICAgIC8vc29sdmUgdGhlIHF1ZXJpZXMKIAogICAgZmNsb3NlKHN0ZGluKTsKICAgIGZjbG9zZShzdGRvdXQpOwogICAgcmV0dXJuIDA7Cn0=