Heavy-Light Decomposition

struct tree {
    int n;
    vector < int > t;

    void build(vector<int> &x) {
        n = x.size();

        int tree_size = 1;
        while ((1ll << tree_size) < n)
            tree_size++;

        t.resize(4 * (1ll << tree_size));

        build(x, 1, 0, n - 1);
    }

    void build(vector <int> &a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) >> 1;
        build(a, v << 1, tl, tm);
        build(a, v << 1 | 1, tm + 1, tr);
        t[v] = t[v << 1] + t[v << 1 | 1];
    }

    void update(int pos, int val, int v, int tl, int tr) {
        if (tl > pos || tr < pos)
            return;
        if (tl == tr && pos == tl) {
            t[v] = val;
            return;
        }
        int tm = (tl + tr) >> 1;
        update(pos, val, v << 1, tl, tm);
        update(pos, val, v << 1 | 1, tm + 1, tr);
        t[v] = t[v << 1] + t[v << 1 | 1];
    }

    int get(int l, int r, int v, int tl, int tr) {
        if (tl > r || tr < l)
            return 0;
        if (l <= tl && tr <= r)
            return t[v];
        int tm = (tl + tr) >> 1;
        return get(l, r, v << 1, tl, tm) +
                get(l, r, v << 1 | 1, tm + 1, tr);
    }

    void update(int pos, int val) {
        update(pos, val, 1, 0, n - 1);
    }

    int get(int l, int r) {
        if (l > r) swap(l, r);
        return get(l, r, 1, 0, n - 1);
    }
};

struct HLD {
    int n, root;
    vector < vector <int> > g;

    vector < int > sz;
    vector < int > depth;
    vector < int > parent;

    vector < int > decompose;
    vector < int > pos;
    tree t;

    vector < int > top;

    void build(vector < vector<int> > &adj, vector < int > &cost, int _root) {
        n = adj.size() - 1;
        root = _root;
        g = adj;

        sz.resize(n + 1);
        depth.resize(n + 1);
        parent.resize(n + 1);

        init(root);

        top.resize(n + 1);

        dfs(root, root);

        pos.resize(n + 1);
        for (int i = 0; i < n; i++)
            pos[decompose[i]] = i;

        for (int i = 1; i <= n; i++)
            decompose[i - 1] = cost[decompose[i - 1]];

        t.build(decompose);
    }

    void init(int v, int d = 0, int p = 1) {
        sz[v]++;
        depth[v] = d;
        parent[v] = p;

        for (auto to : g[v])
            if (to != p)
                init(to, d + 1, v), sz[v] += sz[to];
    }

    void dfs(int v, int cur_top) {
        decompose.push_back(v);
        top[v] = cur_top;

        if (v != root && g[v].size() == 1)
            return;

        int next_heavy = 0;
        for (auto to : g[v])
            if (sz[to] > sz[next_heavy] && to != parent[v])
                next_heavy = to;

        dfs(next_heavy, cur_top);

        for (auto to : g[v])
            if (to != next_heavy && to != parent[v])
                dfs(to, to);
    }

    int lca(int u, int v) {
        while (top[u] != top[v])
            if (depth[top[u]] > depth[top[v]])
                u = parent[top[u]];
            else
                v = parent[top[v]];
        return (depth[u] < depth[v] ? u : v);
    }

    int get(int u, int v) {
        int l = lca(u, v);
        int res = 0;
        while (top[u] != top[l]) {
            res += t.get(pos[u], pos[top[u]]);
            u = parent[top[u]];
        }
        res += t.get(pos[u], pos[l]);
        while (top[v] != top[l]) {
            res += t.get(pos[v], pos[top[v]]);
            v = parent[top[v]];
        }
        res += t.get(pos[v], pos[l]);
        return res - t.get(pos[l], pos[l]);
    }

    void update(int s, int val) {
        t.update(pos[s], val);
    }
};