Under 20m

Not_bad

/*
    Look at me!
    Look at me!
    Look at how large the monster inside me has become!
*/
 
#include<fstream>
#include<cstdio>
#include<map>
#include<set>
#define FIT(a,b) for(vector<int >::iterator a=b.begin();a!=b.end();a++)
#define FITP(a,b) for(vector<pair<int,int> >::iterator a=b.begin();a!=b.end();a++)
#define RIT(a,b) for(vector<int>::reverse_iterator a=b.end();a!=b.begin();++a)
#include<stack>
#define ROF(a,b,c) for(int a=b;a>=c;--a)
#include<vector>
#include<algorithm>
#define FOR(a,b,c) for(int a=b;a<=c;++a)
#define REP(a,b) for(register int a=0;a<b;++a)
#include<cstring>
#include<ctime>
#include<bitset>
#include<cmath>
#include<iomanip>
#include<set>
#define f cin
#define g cout
#include<queue>
#define debug cerr<<"OK";
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ull unsigned long long
#define mod 1000000007
#define MOD 32416190071
#define N 100100
#define SQR 350
#define inf 1<<30
#define div pula
#define hash pizda
using namespace std;
 
ifstream f("heavypath.in");
ofstream g("heavypath.out");
 
vector<int> v[N],P[N],H[N];
int T[N],lvl[N],arb[N],tip,n,m,x,y,nrl,poz[N],cs,lant[N],a[N];
void dfs(int x,int l,int p)
{
    T[x]=p;
    lvl[x]=l;
    arb[x]=1;
    int best=0;
 
    FIT(it,v[x])
    if(*it!=p)
    {
        dfs(*it,l+1,x);
        arb[x]+=arb[*it];
        if(arb[*it]>arb[best])
            best=*it;
    }
 
    if(!best)
    {
        ++nrl;
        P[nrl].pb(0);
        P[nrl].pb(x);
        poz[x]=1;
        lant[x]=nrl;
        return ;
    }
 
    lant[x]=lant[best];
    P[lant[x]].pb(x);
    poz[x]=P[lant[x]].size()-1;
}
void qr(int lant,int st,int dr,int po,int l,int r)
{
    if(st>=l&&dr<=r)
    {
        cs=max(cs,H[lant][po]);
        return ;
    }
    int mij=(st+dr)>>1;
    if(l<=mij)
    qr(lant,st,mij,po<<1,l,r);
    if(r>mij)
    qr(lant,mij+1,dr,(po<<1)+1,l,r);
}
void upd(int lant,int st,int dr,int po,int poz)
{
    if(st==dr)
    {
        H[lant][po]=a[P[lant][poz]];
        return;
    }
    int mij=(st+dr)>>1;
    if(poz<=mij)
    upd(lant,st,mij,po<<1,poz);
    else
    upd(lant,mij+1,dr,(po<<1)+1,poz);
    H[lant][po]=max(H[lant][po<<1],H[lant][(po<<1)+1]);
}
void go(int lant,int st,int dr,int po)
{
    if(st==dr)
    {
        H[lant][po]=a[P[lant][st]];
        return ;
    }
    int mij=(st+dr)>>1;
    go(lant,st,mij,po<<1);
    go(lant,mij+1,dr,(po<<1)+1);
    H[lant][po]=max(H[lant][po<<1],H[lant][(po<<1)+1]);
}
int find(int x,int y)
{
    cs=-(1<<30);
    while(1)
    {
        if(lant[x]==lant[y])
        {
            int st=poz[x];
            int dr=poz[y];
            if(st>dr)
            swap(st,dr);
            qr(lant[x],1,P[lant[x]].size()-1,1,st,dr);
            return cs;
        }
        int a=P[lant[x]][1];
        int b=P[lant[y]][1];
        if(lvl[a]<lvl[b])
        swap(x,y);
        qr(lant[x],1,P[lant[x]].size()-1,1,1,poz[x]);
        x=T[P[lant[x]][1]];
    }
}
int main ()
{
    f>>n>>m;
    FOR(i,1,n)
        f>>a[i];
    FOR(i,1,n-1)
    {
        f>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    dfs(1,1,0);
    FOR(i,1,nrl)
    {
        int siz=P[i].size();
        siz--;
        FOR(j,1,siz/2)
        {
            swap(poz[P[i][j]],poz[P[i][siz-j+1]]);
            swap(P[i][j],P[i][siz-j+1]);
        }
        H[i].resize((siz+1)*4);
        go(i,1,siz,1);
    }
    FOR(i,1,m)
    {
        f>>tip;
        if(!tip)
        {
            f>>x>>y;
            a[x]=y;
            upd(lant[x],1,P[lant[x]].size()-1,1,poz[x]);
        }
        else
        {
            f>>x>>y;
            g<<find(x,y)<<"\n";
        }
    }
    return 0;
}