Heavy-light-декомпозиция

struct SegmentTree {
    int size;
    vector<int> t;

    int query(int v, int vl, int vr, int l, int r) {
        if (vr < l || r < vl)
            return -1e9;
        if (l <= vl && vr <= r)
            return t[v];
        int vm = vl + (vr - vl) / 2;
        int ql = query(2 * v + 1, vl, vm, l, r);
        int qr = query(2 * v + 2, vm + 1, vr, l, r);
        return max(ql, qr);
    }

    void modify(int v, int vl, int vr, int index, int value) {
        if (vr < index || index < vl)
            return;
        if (vl == vr) {
            t[v] += value;
            return;
        }
        int vm = vl + (vr - vl) / 2;
        modify(2 * v + 1, vl, vm, index, value);
        modify(2 * v + 2, vm + 1, vr, index, value);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }

    SegmentTree(int size) : size(size), t(4 * size) {}

    int getMax(int l, int r) {
        return query(0, 0, size - 1, l, r);
    }

    void addValue(int index, int value) {
        modify(0, 0, size - 1, index, value);
    }
};

struct HeavyLightDecomposition {
    vector<vector<int>> graph;
    vector<int> l, r, parent, subtreeSize;
    int timer = 0;
    vector<vector<int>> paths;
    vector<int> pathOf, posOf;
    vector<SegmentTree> segmentTrees;

    HeavyLightDecomposition(int vertexCount) :
        graph(vertexCount), l(vertexCount), r(vertexCount),
        parent(vertexCount), subtreeSize(vertexCount),
        pathOf(vertexCount), posOf(vertexCount) {}

    void addEdge(int a, int b) {
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int dfs(int v, int p) {
        l[v] = timer++;
        parent[v] = p;
        subtreeSize[v] = 1;

        for (int to : graph[v])
            if (to != p)
                subtreeSize[v] += dfs(to, v);

        r[v] = timer++;
        return subtreeSize[v];
    }

    bool isAncestor(int a, int b) {
        return l[a] <= l[b] && r[b] <= r[a];
    }

    void buildPath(int v, int pathIndex) {
        if (paths.size() == pathIndex)
            paths.emplace_back();
        paths[pathIndex].push_back(v);

        pathOf[v] = pathIndex;
        posOf[v] = paths[pathIndex].size() - 1;

        int maxTo = -1;
        for (int to : graph[v])
            if (to != parent[v] && (maxTo == -1 || subtreeSize[maxTo] < subtreeSize[to]))
                maxTo = to;

        for (int to : graph[v]) {
            if (to == parent[v])
                continue;
            if (to == maxTo)
                buildPath(to, pathIndex);
            else
                buildPath(to, paths.size());
        }
    }

    void prepare(int root) {
        dfs(root, -1);
        buildPath(root, 0);
        for (vector<int> &path : paths)
            segmentTrees.push_back(SegmentTree(path.size()));
    }

    int getMax(int a, int b) {
        int res = 0;

        for (; !isAncestor(paths[pathOf[a]][0], b); a = parent[paths[pathOf[a]][0]])
            res = max(res, segmentTrees[pathOf[a]].getMax(0, posOf[a]));
        for (; !isAncestor(paths[pathOf[b]][0], a); b = parent[paths[pathOf[b]][0]])
            res = max(res, segmentTrees[pathOf[b]].getMax(0, posOf[b]));

        if (posOf[a] > posOf[b])
            swap(a, b);
        return max(res, segmentTrees[pathOf[a]].getMax(posOf[a], posOf[b]));
    }

    void addValue(int v, int value) {
        segmentTrees[pathOf[v]].addValue(posOf[v], value);
    }
};

Ссылки на задачи

• Timus #1553 — Caves and Tunnels

Ссылки

Теория:

• e-maxx.ru — Heavy-light декомпозиция
• cp-algorithms.com — Heavy-light decomposition
• algorithmica.org — Heavy-light декомпозиция
• codeforces.com — Heavy-light decompositon — это может быть просто!
• codeforces.com — Hybrid Tutorial #-1: Heavy-Light Decomposition
• blog.anudeep2011.com — Heavy Light Decomposition
• usaco.guide — Heavy-Light Decomposition

Код:

• codelibrary/cpp/structures/heavy_light_decomposition.cpp
• algos/Graphs/HLD.cpp
• algos/Graphs/LCAHLD.cpp