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

Материал из Олимпиадное программирование в УлГТУ
Версия от 00:43, 15 февраля 2026; Ctrlalt (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Отдельное дерево отрезков для каждого пути

Изменение порядка рёбер в списках смежности, одно общее дерево отрезков для всех путей 

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

    void build(int v, int vl, int vr, vector<int> &path, vector<int> &values) {
        if (vl == vr) {
            t[v] = values[path[vl]];
            return;
        }
        int vm = vl + (vr - vl) / 2;
        build(2 * v + 1, vl, vm, path, values);
        build(2 * v + 2, vm + 1, vr, path, values);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }

    int query(int v, int vl, int vr, int l, int r) {
        if (l <= vl && vr <= r)
            return t[v];
        int vm = vl + (vr - vl) / 2;
        if (r <= vm)
            return query(2 * v + 1, vl, vm, l, r);
        if (vm + 1 <= l)
            return query(2 * v + 2, vm + 1, vr, l, r);
        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 (vl == vr) {
            t[v] = value;
            return;
        }
        int vm = vl + (vr - vl) / 2;
        if (index <= vm)
            modify(2 * v + 1, vl, vm, index, value);
        else
            modify(2 * v + 2, vm + 1, vr, index, value);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }

    SegmentTree() {}

    SegmentTree(vector<int> &path, vector<int> &values) : size(path.size()), t(4 * size) {
        build(0, 0, size - 1, path, values);
    }

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

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

struct HeavyLightDecomposition {
    vector<vector<int>> graph, paths;
    vector<int> parent, depth, subtreeSize, pathOf, posOf;
    vector<SegmentTree> segmentTrees;

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

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

    int dfs1(int v, int p) {
        parent[v] = p;
        depth[v] = parent[v] != -1 ? depth[parent[v]] + 1 : 0;
        subtreeSize[v] = 1;
        for (int to : graph[v])
            if (to != parent[v])
                subtreeSize[v] += dfs1(to, v);
        return subtreeSize[v];
    }

    void dfs2(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])
                dfs2(to, to == maxTo ? pathIndex : paths.size());
    }

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

    int getMax(int a, int b) {
        int res = -1e9;

        while (pathOf[a] != pathOf[b]) {
            if (depth[paths[pathOf[a]][0]] > depth[paths[pathOf[b]][0]])
                swap(a, b);
            res = max(res, segmentTrees[pathOf[b]].getMax(0, posOf[b]));
            b = parent[paths[pathOf[b]][0]];
        }

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

        return res;
    }

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

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

    void build(int v, int vl, int vr, vector<int> &posInv, vector<int> &values) {
        if (vl == vr) {
            t[v] = values[posInv[vl]];
            return;
        }
        int vm = vl + (vr - vl) / 2;
        build(2 * v + 1, vl, vm, posInv, values);
        build(2 * v + 2, vm + 1, vr, posInv, values);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }

    int query(int v, int vl, int vr, int l, int r) {
        if (l <= vl && vr <= r)
            return t[v];
        int vm = vl + (vr - vl) / 2;
        if (r <= vm)
            return query(2 * v + 1, vl, vm, l, r);
        if (vm + 1 <= l)
            return query(2 * v + 2, vm + 1, vr, l, r);
        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 (vl == vr) {
            t[v] = value;
            return;
        }
        int vm = vl + (vr - vl) / 2;
        if (index <= vm)
            modify(2 * v + 1, vl, vm, index, value);
        else
            modify(2 * v + 2, vm + 1, vr, index, value);
        t[v] = max(t[2 * v + 1], t[2 * v + 2]);
    }

    SegmentTree() {}

    SegmentTree(vector<int> &posInv, vector<int> &values) : size(posInv.size()), t(4 * size) {
        build(0, 0, size - 1, posInv, values);
    }

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

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

struct HeavyLightDecomposition {
    vector<vector<int>> graph;
    vector<int> parent, depth, subtreeSize, pos, posInv, pathStart;
    int timer = 0;
    SegmentTree segmentTree;

    HeavyLightDecomposition(int vertexCount) :
        graph(vertexCount), parent(vertexCount), depth(vertexCount),
        subtreeSize(vertexCount), pos(vertexCount), posInv(vertexCount), pathStart(vertexCount) {}

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

    int dfs1(int v, int p) {
        parent[v] = p;
        if (parent[v] != -1) {
            depth[v] = depth[parent[v]] + 1;
            graph[v].erase(find(graph[v].begin(), graph[v].end(), parent[v]));
        }
        subtreeSize[v] = 1;
        for (int &to : graph[v]) {
            subtreeSize[v] += dfs1(to, v);
            if (subtreeSize[graph[v][0]] < subtreeSize[to])
                swap(graph[v][0], to);
        }
        return subtreeSize[v];
    }

    void dfs2(int v, int start) {
        pos[v] = timer;
        posInv[timer++] = v;
        pathStart[v] = start;
        for (int to : graph[v])
            dfs2(to, to == graph[v][0] ? pathStart[v] : to);
    }

    void prepare(int root, vector<int> &values) {
        dfs1(root, -1);
        dfs2(root, root);
        segmentTree = SegmentTree(posInv, values);
    }

    int getMax(int a, int b) {
        int res = -1e9;

        while (pathStart[a] != pathStart[b]) {
            if (depth[pathStart[a]] > depth[pathStart[b]])
                swap(a, b);
            res = max(res, segmentTree.getMax(pos[pathStart[b]], pos[b]));
            b = parent[pathStart[b]];
        }

        if (depth[a] > depth[b])
            swap(a, b);
        res = max(res, segmentTree.getMax(pos[a], pos[b]));

        return res;
    }

    void setValue(int v, int value) {
        segmentTree.setValue(pos[v], value);
    }
};

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

Ссылки

Теория:

Код:

Источник — https://acm.khpnets.info/w39/index.php?title=Heavy-light-декомпозиция&oldid=2948