/*
Acest program implementează algoritmul Heavy Path Decomposition (HPD) pentru
a rezolva probleme legate de un arbore ponderat. HPD este o tehnică de divizare
a unui arbore în lanțuri, astfel încât lungimea maximă a drumului
de la rădăcină la orice nod să fie minimizată. În acest program, arborele este
construit din noduri ponderate, iar algoritmul HPD este folosit
pentru a răspunde la interogări legate de aceste ponderi.

Programul poate fi divizat în câteva părți principale:

1. Citirea și construirea grafului.
2. Implementarea Heavy Path Decomposition.
3. Construirea și actualizarea arborelui de intervale.
4. Răspunsul la interogări.

**Citirea și construirea grafului (`read_graph`):**

Funcția `read_graph` citește numărul de noduri (n) și numărul de interogări (m),
atribuie ponderi fiecărui nod și construiește arborele
prin adăugarea muchiilor între noduri.

**Implementarea Heavy Path Decomposition (`df`, `make_paths`):**

Funcția `df` este o funcție recursivă de parcurgere în adâncime
(Depth-First Search) care calculează nivelul fiecărui nod în arbore,
dimensiunea subarborelui și descompune arborele în lanțuri.
Dacă nodul curent este o frunză, se creează un nou lanț.
Dacă nu, nodul curent este adăugat la lanțul nodului "heavy"
(cel cu cel mai mare subarbore).

Funcția `make_paths` apelează funcția `df` pentru a realiza descompunerea
și apoi construiește arborele de intervale pentru fiecare lanț.

**Construirea și actualizarea arborelui de intervale (`build`, `update`):**

Funcția `build` construiește arborele de intervale pentru un lanț dat.
Fiecare nod din arborele de intervale conține valoarea maximă
dintre cele două copii.
Funcția `update` este utilizată pentru a actualiza un nod
din arborele de intervale și, implicit, toți strămoșii săi.

**Răspunsul la interogări (`query`, `solve`):**

Funcția `query` interoghează arborele de intervale pentru a găsi
valoarea maximă dintre două noduri pe același lanț.
Funcția `solve` procesează interogările și răspunde la acestea folosind
funcțiile `query` și `update`.

Există două tipuri de interogări:
- Actualizarea valorii unui nod (t = 0).
- Aflarea valorii maxime pe drumul dintre două noduri (t = 1).

Pentru a răspunde la o interogare de tipul 1,
programul parcurge lanțurile de la nodul x la nodul y,
interogând arborele de intervale pentru a obține valoarea maximă
pe fiecare lanț și actualizând soluția cu aceasta.
Procesul se repetă până când nodurile x și y se află pe același lanț.

În cele din urmă, programul afișează răspunsul la interogările de tipul 1.
*/

#include <algorithm>
#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

#define MAXN 100010

int n, m, lanturi;
int a[MAXN], niv[MAXN], g[MAXN], nl[MAXN], aint[4 * MAXN];
bool v[MAXN];
int lTata[MAXN], lNiv[MAXN], d[MAXN], pozl[MAXN];
vector<int> G[MAXN], l[MAXN];
ifstream fin("heavypath.in");

void read_graph() {
    int x, y;
    fin >> n >> m;
    for (int i = 1; i <= n; i++)
        fin >> a[i];
    for (int i = 1; i < n; i++) {
        fin >> x >> y;
        G[x].push_back(y);
        G[y].push_back(x);
    }
}

void df(int nod) {
    int hN = -1;
    bool frunza = true;

    v[nod] = true, g[nod] = 1;
    for (int vecin : G[nod]) {
        if (!v[vecin]) {
            frunza = false;
            niv[vecin] = niv[nod] + 1;
            df(vecin);
            g[nod] += g[vecin];
            if (hN == -1)
                hN = vecin;
            else if (g[hN] < g[vecin])
                hN = vecin;
        }
    }
    if (frunza) {
        nl[nod] = ++lanturi;
        d[lanturi] = 1;
        l[lanturi].push_back(nod);
        return;
    }
    nl[nod] = nl[hN];
    d[nl[nod]]++;
    l[nl[nod]].push_back(nod);
    for (int vecin : G[nod]) {
        if (vecin != hN) {
            lTata[nl[vecin]] = nod;
            lNiv[nl[vecin]] = niv[nod];
        }
    }
}

void build(int nod, int s, int d, int decalaj, int lant) {
    int m;
    if (s < d) {
        m = (s + d) / 2;
        build(nod * 2, s, m, decalaj, lant);
        build(nod * 2 + 1, m + 1, d, decalaj, lant);
        aint[nod + decalaj] = max(aint[nod * 2 + decalaj], aint[nod * 2 + 1 + decalaj]);
    }
    else
        aint[nod + decalaj] = a[l[lant][s - 1]];
}

void make_paths() {
    niv[1] = 1;
    df(1);
    for (int i = 1; i <= lanturi; i++) {
        reverse(l[i].begin(), l[i].end());
        if (i > 1)
            pozl[i] = pozl[i - 1] + d[i - 1] * 4;
        build(1, 1, d[i], pozl[i], i);
    }
}

void update(int nod, int left, int right, int poz, int val, int decalaj) {
    if (left == right) {
        aint[nod + decalaj] = val;
        return;
    }
    int med = (left + right) / 2;
    if (poz <= med)
        update(nod * 2, left, med, poz, val, decalaj);
    else
        update(nod * 2 + 1, med + 1, right, poz, val, decalaj);
    aint[nod + decalaj] = max(aint[nod * 2 + decalaj], aint[nod * 2 + 1 + decalaj]);
}

int query(int nod, int left, int right, int qleft, int qright, int decalaj) {
    if (qleft <= left && right <= qright)
        return aint[nod + decalaj];
    int med = (left + right) / 2, rez = 0;
    if (qleft <= med)
        rez = max(rez, query(nod * 2, left, med, qleft, qright, decalaj));
    if (med < qright)
        rez = max(rez, query(nod * 2 + 1, med + 1, right, qleft, qright, decalaj));
    return rez;
}

void solve() {
    int t, x, y, sol = 0;
    for (int i = 1; i <= m; ++i) {
        fin >> t >> x >> y;
        if (t == 0)
            update(1, 1, d[nl[x]], niv[x] - lNiv[nl[x]], y, pozl[nl[x]]);
        else {
            sol = 0;
            while (1) {
                if (nl[x] == nl[y]) {
                    if (niv[x] > niv[y])
                        swap(x, y);
                    sol = max(sol, query(1, 1, d[nl[x]], niv[x] - lNiv[nl[x]], niv[y] - lNiv[nl[x]], pozl[nl[x]]));
                    break;
                }
                if (lNiv[nl[x]] < lNiv[nl[y]])
                    swap(x, y);
                sol = max(sol, query(1, 1, d[nl[x]], 1, niv[x] - lNiv[nl[x]], pozl[nl[x]]));
                x = lTata[nl[x]];
            }
            printf("%d\n", sol);
        }
    }
}

int main() {
    freopen("heavypath.out", "w", stdout);
    read_graph();
    make_paths();
    solve();
    return 0;
}