#include <cstring>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
const int SIZE = 100002;
int N, M;
int A[SIZE], Son[SIZE], T[SIZE];
vector<int> V[SIZE], Lant[SIZE];
int where[SIZE], whpos[SIZE], sL;
bool heavy[SIZE], isheavy[SIZE];
int RMQ[18][2 * SIZE];
int pNod[2 * SIZE], lvl[2 * SIZE], in[SIZE], eSize;
int LCA(int nod1, int nod2)
{
nod1 = in[nod1], nod2 = in[nod2];
if (nod1 > nod2) swap(nod1, nod2);
int k = 0;
while ((1 << (k + 1)) <= nod2 - nod1 + 1)
++k;
if (lvl[RMQ[k][nod1]] > lvl[RMQ[k][nod2 - (1 << k) + 1]])
return pNod[RMQ[k][nod2 - (1 << k) + 1]];
return pNod[RMQ[k][nod1]];
}
int qPos, Val, result, I1, I2;
int AINT[SIZE * 4];
void update(int nod, int s1, int s2)
{
if (s1 == s2)
{
AINT[nod] = Val;
return;
}
int mid = (s1 + s2) >> 1;
if (qPos <= mid) update(nod * 2, s1, mid);
else update(nod * 2 + 1, mid + 1, s2);
AINT[nod] = max(AINT[nod * 2], AINT[nod * 2 + 1]);
}
void query(int nod, int s1, int s2)
{
if (I1 <= s1 && s2 <= I2)
{
result = max(result, AINT[nod]);
return;
}
int mid = (s1 + s2) >> 1;
if (I1 <= mid) query(nod * 2, s1, mid);
if (I2 > mid) query(nod * 2 + 1, mid + 1, s2);
}
void preDfs(int x)
{
Son[x] = 1;
for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
if (*it != T[x])
{
pNod[++eSize] = *it;
lvl[eSize] = lvl[in[x]] + 1;
in[*it] = eSize;
T[*it] = x;
preDfs(*it);
Son[x] += Son[*it];
pNod[++eSize] = x;
lvl[eSize] = lvl[in[x]];
}
}
void heavy_light(int x)
{
for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
if (*it != T[x] && Son[*it] >= Son[x] / 2)
{
heavy[*it] = true;
isheavy[x] = true;
break;
}
for (vector<int>::iterator it = V[x].begin(); it != V[x].end(); ++it)
if (*it != T[x])
heavy_light(*it);
if (!isheavy[x] && where[x] == 0)
{
int now = x;
++sL;
while (true)
{
++qPos;
Val = A[now];
update(1, 1, N);
Lant[sL].push_back(now);
where[now] = sL;
whpos[now] = qPos;
if (!heavy[now]) break;
now = T[now];
}
}
}
int getResult(int now, int nodLCA)
{
int maxnow = 0;
while (LCA(Lant[where[now]].back(), nodLCA) == nodLCA)
{
result = 0;
I1 = whpos[now], I2 = whpos[Lant[where[now]].back()];
query(1, 1, N);
maxnow = max(maxnow, result);
if (Lant[where[now]].back() == nodLCA)
{
now = nodLCA;
break;
}
now = T[Lant[where[now]].back()];
}
if (now != nodLCA)
{
result = 0;
I1 = whpos[now], I2 = whpos[nodLCA];
query(1, 1, N);
maxnow = max(maxnow, result);
}
return maxnow;
}
int main()
{
ifstream fin("heavypath.in");
ofstream fout("heavypath.out");
fin >> N >> M;
for (int i = 1; i <= N; ++i)
fin >> A[i];
for (int i = 1, nod1, nod2; i < N; ++i)
{
fin >> nod1 >> nod2;
V[nod1].push_back(nod2);
V[nod2].push_back(nod1);
}
pNod[++eSize] = 1;
lvl[eSize] = 0;
in[1] = eSize;
preDfs(1);
heavy_light(1);
for (int i = 1; i < 2 * N; ++i)
RMQ[0][i] = i;
for (int i = 1; (1 << i) < 2 * N; ++i)
for (int j = 1; j < 2 * N; ++j)
{
RMQ[i][j] = RMQ[i - 1][j];
if (j + (1 << (i - 1)) < 2 * N && lvl[RMQ[i][j]] > lvl[RMQ[i - 1][j + (1 << (i - 1))]])
RMQ[i][j] = RMQ[i - 1][j + (1 << (i - 1))];
}
for (int i = 1, t, x, y; i <= M; ++i)
{
fin >> t >> x >> y;
if (t == 0)
{
qPos = whpos[x];
Val = y;
update(1, 1, N);
}
else
{
int nodLCA = LCA(x, y), maxnow = 0;
maxnow = max(getResult(x, nodLCA), getResult(y, nodLCA));
fout << maxnow << '\n';
}
}
fin.close();
fout.close();
}