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

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

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

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); } };

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

• 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