Heavy Light Decomposition

hld.cpp

#include <bits/stdc++.h>

using namespace std;
typedef int ll;

class SegmentTree {
    struct Node {
        pair<ll, ll> range;
        ll left = 0, right = 0, value = 0;
    };

    vector<Node> node;

    void build(ll id, ll l, ll r) {
        node[id].range = {l, r};

        if (l == r) {
            return;
        }

        node[id].left = id * 2;
        node[id].right = id * 2 + 1;

        build(node[id].left, l, (l + r) / 2);
        build(node[id].right, (l + r) / 2 + 1, r);
    }

    void _update(ll id, ll i, ll val) {
        if (id == 0) {
            return;
        }

        auto [l, r] = node[id].range;

        if (i < l || r < i) {
            return;
        }

        if (l == r) {
            node[id].value = val;
            return;
        }

        _update(node[id].left, i, val);
        _update(node[id].right, i, val);

        node[id].value = max(node[node[id].left].value, node[node[id].right].value);
    }

    ll _query(ll id, ll a, ll b) {
        if (id == 0) {
            return 0;
        }

        auto [l, r] = node[id].range;

        if (b < l || r < a) {
            return 0;
        }

        if (a <= l && r <= b) {
            return node[id].value;
        }

        return max(_query(node[id].left, a, b), _query(node[id].right, a, b));
    }

   public:
    SegmentTree() {}

    SegmentTree(ll n) {
        node.resize(4 * n);
        build(1, 0, n - 1);
    }

    void update(ll i, ll x) {
        _update(1, i, x);
    }

    ll query(ll l, ll r) {
        return _query(1, l, r);
    }
};

class Tree {
    struct Vertex {
        ll parent, depth, root, pos, heavy = -1;
    };

    vector<vector<ll>> graph;
    vector<Vertex> vx;
    SegmentTree st;
    ll curPos = 0;

    ll dfs(ll u, ll p, ll d) {
        vx[u].parent = p;
        vx[u].depth = d;

        ll size = 1;
        ll maxChildSize = 0;

        for (ll v : graph[u]) {
            if (v == p) {
                continue;
            }

            ll childSize = dfs(v, u, d + 1);

            size += childSize;

            if (childSize > maxChildSize) {
                maxChildSize = childSize;
                vx[u].heavy = v;
            }
        }

        return size;
    }

    void flatten(ll u, ll root) {
        vx[u].root = root;
        vx[u].pos = curPos++;

        if (vx[u].heavy != -1) {
            flatten(vx[u].heavy, root);
        }

        for (ll v : graph[u]) {
            if (v == vx[u].parent || v == vx[u].heavy) {
                continue;
            }

            flatten(v, v);
        }
    }

   public:
    void add_edge(ll u, ll v) {
        graph[u].push_back(v);
        graph[v].push_back(u);
    }

    void decompose() {
        dfs(0, -1, 0);
        flatten(0, 0);
    }

    void update(ll u, ll val) {
        st.update(vx[u].pos, val);
    }

    ll query(ll a, ll b) {
        ll res = 0;

        while (vx[a].root != vx[b].root) {
            if (vx[vx[a].root].depth > vx[vx[b].root].depth) {
                swap(a, b);
            }

            res = max(res, st.query(vx[vx[b].root].pos, vx[b].pos));
            b = vx[vx[b].root].parent;
        }

        if (vx[a].depth > vx[b].depth) {
            swap(a, b);
        }

        res = max(res, st.query(vx[a].pos, vx[b].pos));

        return res;
    }

    Tree(ll n) {
        graph.resize(n);
        vx.resize(n);
        st = SegmentTree(n);
    }
};

int main() {
    ios::sync_with_stdio(0);
    cout.tie(0);
    cin.tie(0);

    ll n, q;
    cin >> n >> q;

    Tree tree(n);
    vector<ll> v(n);

    for (auto& i : v) {
        cin >> i;
    }

    for (ll i = 0; i < n - 1; i++) {
        ll u, v;
        cin >> u >> v;

        tree.add_edge(u - 1, v - 1);
    }

    tree.decompose();

    for (ll i = 0; i < n; i++) {
        tree.update(i, v[i]);
    }

    while (q--) {
        ll type;
        cin >> type;

        if (type == 1) {
            ll s, x;
            cin >> s >> x;

            tree.update(s - 1, x);
        } else {
            ll a, b;
            cin >> a >> b;

            cout << tree.query(a - 1, b - 1) << ' ';
        }
    }
}