Heavy-light-декомпозиция - История изменений

Ctrlalt в 00:43, 15 февраля 2026

2026-02-15T00:43:22Z

Ctrlalt в 22:35, 14 февраля 2026

2026-02-14T22:35:34Z

← Предыдущая версия		Версия от 22:35, 14 февраля 2026
Строка 62:		Строка 62:

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

Строка 86:		Строка 86:
	maxTo = to;		maxTo = to;

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

Ctrlalt: /* Ссылки */

2026-02-14T22:29:20Z

Ссылки

← Предыдущая версия		Версия от 22:29, 14 февраля 2026
Строка 125:		Строка 125:

	== Ссылки ==		== Ссылки ==
	* [~~http~~://e-maxx.ru/algo/heavy_light e-maxx.ru ~~—~~ Heavy-light декомпозиция]		Теория:
	* [~~http~~://blog.anudeep2011.com/heavy-light-decomposition/ blog.anudeep2011.com ~~—~~ 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 — 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 — 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 — 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]

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

Ctrlalt в 21:58, 14 февраля 2026

2026-02-14T21:58:56Z

Внесённые изменения

Ctrlalt: Новая страница: « #include #include #include #include #include #include #include using namespace std; class …»

2014-11-15T14:24:22Z

Новая страница: « #include <stdio.h> #include <vector> #include <queue> #include <set> #include <map> #include <algorithm> #include <iostream> using namespace std; class …»

Новая страница

#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

class ST {
int *t, size;
void build(int v, int vl, int vr) {
if (vl == vr) {
t[v] = 0;
return;
}
int vm = vl + (vr - vl) / 2;
build(2 * v + 1, vl, vm);
build(2 * v + 2, vm + 1, vr);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
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)
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 pos, int val) {
if (pos < vl || vr < pos)
return;
if (pos == vl && vl == vr) {
t[v] += val;
return;
}
int vm = vl + (vr - vl) / 2;
modify(2 * v + 1, vl, vm, pos, val);
modify(2 * v + 2, vm + 1, vr, pos, val);
t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}
public:
ST() {}
ST(int n) {
t = new int[4 * n];
size = n;
build(0, 0, size - 1);
}
int query(int l, int r) {
return query(0, 0, size - 1, l, r);
}
void modify(int pos, int val) {
modify(0, 0, size - 1, pos, val);
}
} st[100010];

int n, q, a, b;
char c;
vector<int> g[100010];
int tIn[100010], tOut[100010], timer, size[100010], parent[100010];

void dfs(int v) {
tIn[v] = ++timer;
size[v] = 1;
for (int i = 0; i < g[v].size(); i++) {
if (!tIn[g[v][i]]) {
parent[g[v][i]] = v;
dfs(g[v][i]);
size[v] += size[g[v][i]];
}
}
tOut[v] = ++timer;
}

bool isAncestor(int a, int v) {
return tIn[a] <= tIn[v] && tOut[v] <= tOut[a];
}

int chainInd[100010], chainPos[100010];
int chainSize[100010], chainRoot[100010];
int chainsCount;

void buildHLD(int v, int chain) {
chainInd[v] = chain;
chainPos[v] = chainSize[chain];
chainSize[chain]++;
if (chainSize[chain] == 1)
chainRoot[chain] = v;
int maxChild = -1;
for (int i = 0; i < g[v].size(); i++) {
if (g[v][i] != parent[v] && (maxChild == -1 || size[g[v][i]] > size[g[v][maxChild]]))
maxChild = i;
}
if (maxChild != -1)

for (int i = 0; i < g[v].size(); i++) {
if (g[v][i] == parent[v])
continue;
if (i == maxChild)
buildHLD(g[v][i], chain);
else
buildHLD(g[v][i], chainsCount++);
}
}

int queryHLD(int a, int b) {
int res = 0;
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))
break;
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() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

scanf("%d", &n);
for (int i = 0; i < n - 1; i++) {
scanf("%d%d", &a, &b);
g[a - 1].push_back(b - 1);
g[b - 1].push_back(a - 1);
}

dfs(0);
buildHLD(0, chainsCount++);
for (int i = 0; i < chainsCount; i++)
st[i] = ST(chainSize[i]);

scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf(" %c%d%d", &c, &a, &b);
if (c == 'I')
st[chainInd[a - 1]].modify(chainPos[a - 1], b);
else
printf("%d\n", queryHLD(a - 1, b - 1));
}
}

== Ссылки на задачи ==
* [http://acm.timus.ru/problem.aspx?num=1553 Timus #1553 — Caves and Tunnels]

== Ссылки ==
* [http://e-maxx.ru/algo/heavy_light e-maxx.ru — Heavy-light декомпозиция]
* [http://blog.anudeep2011.com/heavy-light-decomposition/ blog.anudeep2011.com — Heavy Light Decomposition]
* [http://github.com/indy256/codelibrary/blob/master/java/src/HeavyLight.java CodeLibrary — Heavy-light tree decomposition for edges or vertices]
* [http://github.com/ADJA/algos/blob/master/Graphs/HLD.cpp Algos — Heavy-light decomposition with segment trees in paths]
* [http://github.com/ADJA/algos/blob/master/Graphs/LCAHLD.cpp Algos — Finding LCA (Least common ancestor) of two vertices in the tree. Uses heavy-light decomposition]

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