Heavy-light-декомпозиция: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
(Новая страница: « #include <stdio.h> #include <vector> #include <queue> #include <set> #include <map> #include <algorithm> #include <iostream> using namespace std; class …»)
 
Нет описания правки
 
(не показаны 3 промежуточные версии этого же участника)
Строка 1: Строка 1:
#include <stdio.h>
{|width=100%
#include <vector>
|
#include <queue>
Отдельное дерево отрезков для каждого пути
#include <set>
|
#include <map>
Изменение порядка рёбер в списках смежности, одно общее дерево отрезков для всех путей
#include <algorithm>
|-
  #include <iostream>
|
using namespace std;
  struct SegmentTree {
 
    int size;
class ST {
     vector<int> t;
     int *t, size;
     void build(int v, int vl, int vr) {
     void build(int v, int vl, int vr, vector<int> &path, vector<int> &values) {
         if (vl == vr) {
         if (vl == vr) {
             t[v] = 0;
             t[v] = values[path[vl]];
             return;
             return;
         }
         }
         int vm = vl + (vr - vl) / 2;
         int vm = vl + (vr - vl) / 2;
         build(2 * v + 1, vl, vm);
         build(2 * v + 1, vl, vm, path, values);
         build(2 * v + 2, vm + 1, vr);
         build(2 * v + 2, vm + 1, vr, path, values);
         t[v] = max(t[2 * v + 1], t[2 * v + 2]);
         t[v] = max(t[2 * v + 1], t[2 * v + 2]);
     }
     }
     int query(int v, int vl, int vr, int l, int r) {
     int query(int v, int vl, int vr, int l, int r) {
        if (r < vl || vr < l)
            return -(1 << 30);
         if (l <= vl && vr <= r)
         if (l <= vl && vr <= r)
             return t[v];
             return t[v];
         int vm = vl + (vr - vl) / 2;
         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 ql = query(2 * v + 1, vl, vm, l, r);
         int qr = query(2 * v + 2, vm + 1, vr, l, r);
         int qr = query(2 * v + 2, vm + 1, vr, l, r);
         return max(ql, qr);
         return max(ql, qr);
     }
     }
     void modify(int v, int vl, int vr, int pos, int val) {
         if (pos < vl || vr < pos)
     void modify(int v, int vl, int vr, int index, int value) {
            return;
         if (vl == vr) {
        if (pos == vl && vl == vr) {
             t[v] = value;
             t[v] += val;
             return;
             return;
         }
         }
         int vm = vl + (vr - vl) / 2;
         int vm = vl + (vr - vl) / 2;
         modify(2 * v + 1, vl, vm, pos, val);
         if (index <= vm)
         modify(2 * v + 2, vm + 1, vr, pos, val);
            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]);
         t[v] = max(t[2 * v + 1], t[2 * v + 2]);
     }
     }
  public:
   
     ST() {}
     SegmentTree() {}
     ST(int n) {
        t = new int[4 * n];
     SegmentTree(vector<int> &path, vector<int> &values) : size(path.size()), t(4 * size) {
        size = n;
         build(0, 0, size - 1, path, values);
         build(0, 0, size - 1);
     }
     }
     int query(int l, int r) {
     int getMax(int l, int r) {
         return query(0, 0, size - 1, l, r);
         return query(0, 0, size - 1, l, r);
     }
     }
     void modify(int pos, int val) {
         modify(0, 0, size - 1, pos, val);
     void setValue(int index, int value) {
         modify(0, 0, size - 1, index, value);
     }
     }
  } st[100010];
  };


  int n, q, a, b;
  struct HeavyLightDecomposition {
char c;
    vector<vector<int>> graph, paths;
  vector<int> g[100010];
    vector<int> parent, depth, subtreeSize, pathOf, posOf;
int tIn[100010], tOut[100010], timer, size[100010], parent[100010];
    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;
   
   
void dfs(int v) {
        int maxTo = -1;
    tIn[v] = ++timer;
        for (int to : graph[v])
    size[v] = 1;
            if (to != parent[v] && (maxTo == -1 || subtreeSize[maxTo] < subtreeSize[to]))
     for (int i = 0; i < g[v].size(); i++) {
                maxTo = to;
         if (!tIn[g[v][i]]) {
             parent[g[v][i]] = v;
        for (int to : graph[v])
             dfs(g[v][i]);
            if (to != parent[v])
             size[v] += size[g[v][i]];
                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;
     }
     }
    tOut[v] = ++timer;
}
   
   
bool isAncestor(int a, int v) {
    void setValue(int v, int value) {
    return tIn[a] <= tIn[v] && tOut[v] <= tOut[a];
        segmentTrees[pathOf[v]].setValue(posOf[v], value);
  }
    }
 
  };
  int chainInd[100010], chainPos[100010];
|
int chainSize[100010], chainRoot[100010];
struct SegmentTree {
int chainsCount;
    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]);
    }
   
   
void buildHLD(int v, int chain) {
    int query(int v, int vl, int vr, int l, int r) {
    chainInd[v] = chain;
        if (l <= vl && vr <= r)
    chainPos[v] = chainSize[chain];
            return t[v];
    chainSize[chain]++;
        int vm = vl + (vr - vl) / 2;
    if (chainSize[chain] == 1)
        if (r <= vm)
         chainRoot[chain] = v;
            return query(2 * v + 1, vl, vm, l, r);
    int maxChild = -1;
         if (vm + 1 <= l)
    for (int i = 0; i < g[v].size(); i++) {
            return query(2 * v + 2, vm + 1, vr, l, r);
         if (g[v][i] != parent[v] && (maxChild == -1 || size[g[v][i]] > size[g[v][maxChild]]))
        int ql = query(2 * v + 1, vl, vm, l, r);
            maxChild = i;
        int qr = query(2 * v + 2, vm + 1, vr, l, r);
         return max(ql, qr);
     }
     }
    if (maxChild != -1)
       
     void modify(int v, int vl, int vr, int index, int value) {
     for (int i = 0; i < g[v].size(); i++) {
         if (vl == vr) {
         if (g[v][i] == parent[v])
            t[v] = value;
             continue;
             return;
         if (i == maxChild)
        }
             buildHLD(g[v][i], chain);
        int vm = vl + (vr - vl) / 2;
         if (index <= vm)
             modify(2 * v + 1, vl, vm, index, value);
         else
         else
             buildHLD(g[v][i], chainsCount++);
             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 queryHLD(int a, int b) {
    int getMax(int l, int r) {
    int res = 0;
         return query(0, 0, size - 1, l, r);
    while (1) {
         if (isAncestor(chainRoot[chainInd[a]], b))
            break;
        res = max(res, st[chainInd[a]].query(0, chainPos[a]));
        a = parent[chainRoot[chainInd[a]]];
     }
     }
     while (1) {
         if (isAncestor(chainRoot[chainInd[b]], a))
     void setValue(int index, int value) {
            break;
         modify(0, 0, size - 1, index, value);
        res = max(res, st[chainInd[b]].query(0, chainPos[b]));
        b = parent[chainRoot[chainInd[b]]];
     }
     }
    if (chainPos[a] > chainPos[b])
  };
        swap(a, b);
    return max(res, st[chainInd[a]].query(chainPos[a], chainPos[b]));
  }


  int main() {
  struct HeavyLightDecomposition {
     freopen("input.txt", "r", stdin);
    vector<vector<int>> graph;
     freopen("output.txt", "w", stdout);
     vector<int> parent, depth, subtreeSize, pos, posInv, pathStart;
     int timer = 0;
    SegmentTree segmentTree;
   
   
     scanf("%d", &n);
     HeavyLightDecomposition(int vertexCount) :
    for (int i = 0; i < n - 1; i++) {
        graph(vertexCount), parent(vertexCount), depth(vertexCount),
        scanf("%d%d", &a, &b);
        subtreeSize(vertexCount), pos(vertexCount), posInv(vertexCount), pathStart(vertexCount) {}
         g[a - 1].push_back(b - 1);
         g[b - 1].push_back(a - 1);
    void addEdge(int a, int b) {
         graph[a].push_back(b);
         graph[b].push_back(a);
     }
     }
   
   
     dfs(0);
     int dfs1(int v, int p) {
    buildHLD(0, chainsCount++);
        parent[v] = p;
    for (int i = 0; i < chainsCount; i++)
        if (parent[v] != -1) {
         st[i] = ST(chainSize[i]);
            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);
    }
   
   
     scanf("%d", &q);
     void prepare(int root, vector<int> &values) {
    for (int i = 0; i < q; i++) {
        dfs1(root, -1);
         scanf(" %c%d%d", &c, &a, &b);
        dfs2(root, root);
         if (c == 'I')
         segmentTree = SegmentTree(posInv, values);
             st[chainInd[a - 1]].modify(chainPos[a - 1], b);
    }
         else
             printf("%d\n", queryHLD(a - 1, b - 1));
    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);
     }
     }
  }
  };
|}


== Ссылки на задачи ==
== Ссылки на задачи ==
Строка 155: Строка 260:


== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/heavy_light e-maxx.ru &mdash; Heavy-light декомпозиция]
Теория:
* [http://blog.anudeep2011.com/heavy-light-decomposition/ blog.anudeep2011.com &mdash; Heavy Light Decomposition]
* [https://e-maxx.ru/algo/heavy_light e-maxx.ru — Heavy-light декомпозиция]
* [http://github.com/indy256/codelibrary/blob/master/java/src/HeavyLight.java CodeLibrary &mdash; Heavy-light tree decomposition for edges or vertices]
* [https://cp-algorithms.com/graph/hld.html cp-algorithms.com — Heavy-light decomposition]
* [http://github.com/ADJA/algos/blob/master/Graphs/HLD.cpp Algos &mdash; Heavy-light decomposition with segment trees in paths]
* [https://algorithmica.org/ru/hld algorithmica.org — Heavy-light декомпозиция]
* [http://github.com/ADJA/algos/blob/master/Graphs/LCAHLD.cpp Algos &mdash; Finding LCA (Least common ancestor) of two vertices in the tree. Uses heavy-light decomposition]
* [https://codeforces.com/blog/entry/12239 codeforces.com — Heavy-light decompositon — это может быть просто!]
* [https://codeforces.com/blog/entry/81317 codeforces.com — Hybrid Tutorial #-1: Heavy-Light Decomposition]
* [https://web.archive.org/web/20221128105153/https://blog.anudeep2011.com/heavy-light-decomposition/ blog.anudeep2011.com — Heavy Light Decomposition]
* [https://usaco.guide/plat/hld usaco.guide — Heavy-Light Decomposition]
Код:
* [https://github.com/indy256/codelibrary/blob/main/cpp/structures/heavy_light_decomposition.cpp codelibrary/cpp/structures/heavy_light_decomposition.cpp]
* [https://github.com/ADJA/algos/blob/master/Graphs/HLD.cpp algos/Graphs/HLD.cpp]
* [https://github.com/ADJA/algos/blob/master/Graphs/LCAHLD.cpp algos/Graphs/LCAHLD.cpp]


[[Категория:Учебный курс «Алгоритмы и структуры данных»]]
[[Категория:Учебный курс «Алгоритмы и структуры данных»]]

Текущая версия от 00:43, 15 февраля 2026

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

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

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