#include <fstream>
#include <vector>
#include <algorithm>
#include <cassert>
#define LeftSon (node << 1)
#define RightSon ((node << 1) + 1)
using namespace std;
const int NMax = 100010, MMax = 100010;
int ans_query;
int N, M;
vector <int> G[NMax];
int aint[4 * NMax];
bool viz[NMax];
int v[NMax];
int nrlanturi;
int tatanod[NMax], tatalant[NMax], nivel[NMax];
int heavy[NMax]; /// heavy[node] = cat de "greu" e subarborele lui node adica cat de multe noduri sunt in subarborele lui
int lant_of[NMax]; /// lant_of[node] = numarul lantului din care face parte node
int start[NMax]; /// start[i] = pozitia de start din vectorul de aint-uri a lantului i
int size[NMax]; /// size[i] = lumgimea lantului i
int poz[NMax]; /// poz[node] = pozitia in lantul lui node a lui node
vector <int> lant[NMax]; /// lant[i] tine toate nodurile din al i-lea lant in ordine crescatoare dupa inaltime
inline void DFS(const int node, const int father)
{
heavy[node] = 1;
nivel[node] = nivel[father] + 1;
tatanod[node] = father;
viz[node] = true;
bool frunza = true;
int heaviest_fiu, max_heavy = 0;
for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++ it)
{
if (!viz[*it])
{
frunza = false;
DFS(*it, node);
heavy[node] += heavy[*it];
if (heavy[*it] > max_heavy)
{
max_heavy = heavy[*it];
heaviest_fiu = *it;
}
}
}
if (frunza)
{
++nrlanturi;
lant_of[node] = nrlanturi;
lant[nrlanturi].push_back(node);
}
else
{
for (vector <int> :: iterator it = G[node].begin(); it != G[node].end(); ++ it)
{
/// la fii care sunt diferiti de cel care are max_heavy le incheiem lantu si punem tatalant
/// la lantu lu ala care e heaviest_fiu il incheiem cu node
if (*it != father)
{
if (*it == heaviest_fiu)
{
lant_of[node] = lant_of[heaviest_fiu];
lant[lant_of[heaviest_fiu]].push_back(node);
}
else
{
tatalant[lant_of[*it]] = node;
}
}
}
}
}
inline void Build(const int node, const int st, const int dr, const int delay, const int index)
{
if (st == dr)
{
aint[delay + node] = v[lant[index][st - 1]];
return ;
}
int mij = (st+dr) >> 1;
Build(LeftSon, st, mij, delay, index);
Build(RightSon, mij + 1, dr, delay, index);
aint[delay + node] = max(aint[delay + LeftSon], aint[delay + RightSon]);
}
inline void Update(const int node, const int st, const int dr, const int delay, const int index, const int p)
{
if (st == dr)
{
aint[delay + node] = v[lant[index][p - 1]];
return ;
}
int mij = (st + dr) >> 1;
if (p <= mij)
Update(LeftSon, st, mij, delay, index, p);
else
Update(RightSon, mij + 1, dr, delay, index, p);
aint[delay + node] = max(aint[delay + LeftSon], aint[delay + RightSon]);
}
inline void Query(const int node, const int st, const int dr, const int delay, const int LeftBound, const int RightBound)
{
if (LeftBound <= st && dr <= RightBound)
{
ans_query = max(ans_query, aint[delay + node]);
return ;
}
int mij = (st + dr) >> 1;
if (LeftBound <= mij)
Query(LeftSon, st, mij, delay, LeftBound, RightBound);
if (mij < RightBound)
Query(RightSon, mij + 1, dr, delay, LeftBound, RightBound);
}
void reverse_start_size_lant(const int i)
{
reverse(lant[i].begin(), lant[i].end());
size[i] = 4 * lant[i].size();
start[i] = start[i-1] + size[i-1];
int pz = 0;
for (vector <int> :: iterator it = lant[i].begin(); it != lant[i].end(); ++ it)
poz[*it] = ++pz;
}
void Precalc_Heavy_Path_Decomposition()
{
DFS(1, 0);
start[1] = 1;
size[1] = 4 * lant[1].size();
reverse(lant[1].begin(), lant[1].end());
int pz = 0;
for (vector <int> :: iterator it = lant[1].begin(); it != lant[1].end(); ++ it)
poz[*it] = ++pz;
for (int i = 2; i <= nrlanturi; ++ i)
reverse_start_size_lant(i);
for (int i = 1; i <= nrlanturi; ++ i)
Build(1, 1, lant[i].size(), start[i], i);
}
int main()
{
ifstream f("heavypath.in");
f >> N >> M;
for (int i = 1; i <= N; ++ i)
f >> v[i];
for (int i = 1; i < N; ++ i)
{
int x, y; f >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
Precalc_Heavy_Path_Decomposition();
ofstream g("heavypath.out");
while (M -- )
{
int code; f >> code;
if (code == 0)
{
/// update
int x, y; f >> x >> y;
v[x] = y;
Update(1, 1, lant[lant_of[x]].size(), start[lant_of[x]], lant_of[x], poz[x]);
}
else
{
/// query
int x, y; f >> x >> y;
ans_query = -1;
while (lant_of[x] != lant_of[y])
{
if (nivel[x] > nivel[y])
swap(x, y);
Query(1, 1, lant[lant_of[y]].size(), start[lant_of[y]], 1, poz[y]);
y = tatalant[lant_of[y]];
}
if (nivel[x] > nivel[y])
swap(x, y);
assert(poz[x] <= poz[y]);
Query(1, 1, lant[lant_of[x]].size(), start[lant_of[x]], poz[x], poz[y]);
g << ans_query << "\n";
}
}
f.close();
g.close();
return 0;
}