heavypath

#include <fstream>
#include <vector>
#include <algorithm>
#define MAXN 100010
using namespace std;
vector<int>v[MAXN];
int up[MAXN],sub[MAXN],lant[MAXN],poz[MAXN],val[MAXN],niv[MAXN],father[MAXN];
int lanturi,Length[MAXN],Max,arb[500010],Decalaj[MAXN];
int m,n;
void DF(int x)
{
  int i;
  int longest=0;
  sub[x]=1;
  for(i=0;i<v[x].size();i++)
  if(!niv[v[x][i]])
  {
    father[v[x][i]]=x;
    niv[v[x][i]]=niv[x]+1;
    DF(v[x][i]);
    sub[x]+=sub[v[x][i]];
    if(sub[v[x][i]]>sub[longest]) longest=v[x][i];
  }
  if(v[x].size()==1 and x!=1){ lanturi++; lant[x]=lanturi; }
  else lant[x]=lant[longest];
  longest=lant[x];
  Length[longest]++;
  poz[x]=Length[longest];
  up[longest]=x;
}
void update(int Lant,int x,int y,int nod,int l,int r)
{
  if(l==r)
  {
    arb[Lant+nod]=y;
    return;
  }
  int m=(l+r)/2;
  if(x<=m) update(Lant,x,y,2*nod,l,m);
  if(x>m) update(Lant,x,y,2*nod+1,m+1,r);
  arb[Lant+nod]=max(arb[Lant+2*nod],arb[Lant+2*nod+1]);
}
void query2(int Lant,int x,int y,int nod,int l,int r)
{
  if(x<=l and y>=r)
  {
    if(Max<arb[Lant+nod]) Max=arb[Lant+nod];
    return;
  }
  int m=(l+r)/2;
  if(x<=m) query2(Lant,x,y,2*nod,l,m);
  if(y>m) query2(Lant,x,y,2*nod+1,m+1,r);

}
void main_query(int x,int y)
{
  int a,b;
  if(lant[x]==lant[y])
  {
    a=min(poz[x],poz[y]);
    b=max(poz[x],poz[y]);
    query2(Decalaj[lant[x]],a,b,1,1,Length[lant[x]]);
    return;
  }
  if(niv[up[lant[x]]]>niv[up[lant[y]]])
  {
    a=1;
    b=poz[x];
    query2(Decalaj[lant[x]],a,b,1,1,Length[lant[x]]);
    main_query(father[up[lant[x]]],y);
    return;
  }
  if(niv[up[lant[x]]]<=niv[up[lant[y]]])
  {
    a=1;
    b=poz[y];
    query2(Decalaj[lant[y]],a,b,1,1,Length[lant[y]]);
    main_query(x,father[up[lant[y]]]);
  }
}
int main()
{
    int i,t,x,y;
    ifstream fi("heavypath.in");
    ofstream fo("heavypath.out");
    fi>>n>>m;
    for(i=1;i<=n;i++) fi>>val[i];
    for(i=1;i<n;i++)
    {
      fi>>x>>y;
      v[x].push_back(y);
      v[y].push_back(x);
    }
    niv[1]=1;
    DF(1);

    for(i=1;i<=lanturi;i++) Decalaj[i]=Length[i-1]+Decalaj[i-1];
    for(i=1;i<=n;i++)
    {
      poz[i]=Length[lant[i]]-poz[i]+1;
      update(Decalaj[lant[i]],poz[i],val[i],1,1,Length[lant[i]]);
    }
    for(i=1;i<=m;i++)
    {
      fi>>t>>x>>y;
      if(t==0)
      {
        update(Decalaj[lant[x]],poz[x],y,1,1,Length[lant[x]]);
      } else
      {
        Max=0;
        main_query(x,y);
        fo<<Max<<"\n";
      }
    }
    return 0;
}