struct Hld {
    struct Segtree {
        int n;
        vector<int> t;
        void build(int v, int tl, int tr, vector<int>& a) {
            if (tl == tr) t[v] = a[tl];
            else {
                int tm = (tl + tr) / 2;
                build(v * 2, tl, tm, a); build(v * 2 + 1, tm + 1, tr, a);
                t[v] = max(t[v * 2], t[v * 2 + 1]);
            }
        }
        Segtree() {}
        void init(vector<int>& a) {
            n = (int)a.size();
            t.resize(4 * n, -inf);
            build(1, 0, n - 1, a);
        }
        void update(int v, int tl, int tr, int pos, int now) {
            if (tl == tr)  t[v] = now;
            else {
                int tm = (tl + tr) / 2;
                if (pos <= tm)update(v * 2, tl, tm, pos, now);
                else update(v * 2 + 1, tm + 1, tr, pos, now);
                t[v] = max(t[v * 2], t[v * 2 + 1]);
            }
        }
        int get_mx(int v, int tl, int tr, int l, int r) {
            if (tr<l || tl>r)return -inf;
            if (tl >= l && tr <= r)return t[v];
            int tm = (tl + tr) / 2;
            return max(get_mx(v * 2, tl, tm, l, r), get_mx(v * 2 + 1, tm + 1, tr, l, r));
        }
    };

    vector<vector<int>> gr;
    int t, Size_n;
    vector<int> siz, tin, tout, head, euler_dfs, p, w;

    Hld() {}
    Hld(int _n) :Size_n(_n) {
        w.resize(Size_n), gr.resize(Size_n);
    }
    inline void Scan_weight() {
        for (int& i : w)cin >> i;
    }
    inline void Scan_tree() {
        for (int i = 0; i < Size_n - 1; i++) {
            int u, v;
            cin >> u >> v;
            u--, v--;
            gr[u].push_back(v);
            gr[v].push_back(u);
        }
    }

    void sizes(int v, int pr) {
        p[v] = pr, siz[v] = 1;
        gr[v].erase(find(all(gr[v]), pr));
        for (int& u : gr[v]) {
            sizes(u, v);
            siz[v] += siz[u];
            if (siz[u] > siz[gr[v][0]]) {
                swap(u, gr[v][0]);
            }
        }
    }
    void hld(int v) {
        tin[v] = t++; euler_dfs.push_back(w[v]);
        for (int& u : gr[v]) {
            if (u == gr[v][0]) head[u] = head[v];
            else head[u] = u;
            hld(u);
        }
        tout[v] = t;
    }
    Segtree Euler;
    void build() {
        gr[0].push_back(0);
        t = 0;
        siz.resize(Size_n), tin.resize(Size_n), tout.resize(Size_n), head.resize(Size_n), p.resize(Size_n);
        sizes(0, 0);
        hld(0);
        Euler.init(euler_dfs);
    }

    inline void up(int& u, int& v, int& ans, auto& ancestor) {
        while (!ancestor(head[u], v)) {
            ans = max(ans, Euler.get_mx(1, 0, Euler.n - 1, tin[head[u]], tin[u]));
            u = p[head[u]];
        }
    }

    int get_max(int u, int v) {
        auto ancestor = [&](const int& u, const int& v) {
            return tin[u] <= tin[v] && tout[u] > tin[v];
        };
        int ans = -inf;
        up(u, v, ans, ancestor);
        up(v, u, ans, ancestor);
        if (!ancestor(u, v)) swap(u, v);
        ans = max(ans, Euler.get_mx(1, 0, Euler.n - 1, tin[u], tin[v]));
        return ans;
    }
    inline void update(const int& u, const int& new_val) {
        Euler.update(1, 0, Euler.n - 1, tin[u], new_val);
    }
};