These are the notes for Competitive Programming episode 55. Heavy-light decomposition (HLD) cuts a rooted tree into heavy chains so that any path is a few ranges of one array, and a segment tree answers each range. Route Alert asks for the highest danger level on a route, with updates, 2 · 10^5 times: climbing the route is correct but Time Limit Exceeded on a long spine. On a straight line the problem is just range maximum with point updates. In a tree, every village calls its biggest child heavy (the main road), heavy edges form chains that get consecutive positions, and every light edge leads to at most half of the subtree above it, so any path crosses at most log₂ n light edges. Moving the deeper village instead of the deeper chain head prints 9 9 8 7 where 6 9 8 7 is right; calling the first child heavy is still correct but TLE on a caterpillar. A stress test passes. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook
A city's roads form a tree. At every junction one road carries on as the main road: the one that leads to the bigger neighbourhood. House numbers run along each main road one after another, so a stretch of main road is a range of numbers. Turning onto a side lane means at most half of the houses beyond that junction are down there (otherwise that lane would have been the main road). Every turn at least halves what is left, so any trip turns only a few times: a trip is a few stretches of main road.
Problem H1 · Route Alert
(Written for this course, in the style of a Codeforces Div. 1 B / Div. 2 E problem.)
A district has n villages joined by roads into a tree; village 1 is the headquarters and every other village v has a parent p_v. Village v reports a flood danger level a_v. Process q operations:
1 x y: village x now reports danger y;2 x y: print the highest danger on the route from x to y, both ends included.
Constraints: 1 ≤ n, q ≤ 2 · 10^5, 0 ≤ a_v, y ≤ 10^9.
10 5
9 2 5 1 7 3 4 6 8 2
1 1 2 2 4 4 6 3 9
2 8 7
2 10 7
1 1 0
2 10 7
2 5 5
1 (9)
/ \
2 (2) 3 (5)
/ \ |
4 (1) 5 (7) 9 (8)
/ \ |
6 (3) 7 (4) 10 (2)
|
8 (6)
| Operation | Route | Answer |
|---|---|---|
2 8 7 |
8, 6, 4, 7 | 6 |
2 10 7 |
10, 9, 3, 1, 2, 4, 7 | 9 (village 1) |
1 1 0 |
village 1 now 0 | |
2 10 7 |
same route | 8 (village 9) |
2 5 5 |
5 | 7 |
A maximum cannot be "subtracted", so the prefix and LCA formulas of episodes 53 and 54 do not work.
The obvious attempt: climb the route (TLE)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001];
vector<int> ch[200001];
void depths() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
}
int climbMax(int u, int v) { // walk the route, one village at a time
int res = 0;
while (dep[u] > dep[v]) res = max(res, a[u]), u = par[u];
while (dep[v] > dep[u]) res = max(res, a[v]), v = par[v];
while (u != v) res = max({res, a[u], a[v]}), u = par[u], v = par[v];
return max(res, a[u]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
depths();
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) a[x] = y; // village x: danger y
else cout << climbMax(x, y) << "\n";
}
}
6
9
8
7
The maximum test is a caterpillar: a spine of 10^5 villages (1, 3, 5, …, 199 999), each with one extra leaf. Every question goes from the bottom of the spine to the top.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001];
vector<int> ch[200001];
void depths() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
}
int climbMax(int u, int v) { // walk the route, one village at a time
int res = 0;
while (dep[u] > dep[v]) res = max(res, a[u]), u = par[u];
while (dep[v] > dep[u]) res = max(res, a[v]), v = par[v];
while (u != v) res = max({res, a[u], a[v]}), u = par[u], v = par[v];
return max(res, a[u]);
}
int main() {
n = 200000; // a long spine, one leaf on every spine village
for (int v = 1; v <= n; v++) a[v] = v % 1000;
for (int v = 2; v <= n; v++) {
par[v] = v % 2 == 0 ? v - 1 : v - 2; // leaf first, then the spine
ch[par[v]].push_back(v);
}
depths();
ll sum = 0;
for (int i = 0; i < 200000; i++) // updates and deep queries
if (i % 2 == 0) a[1 + i % n] = i % 1000;
else sum += climbMax(199999 - 2 * (i % 1000), 2);
cout << sum << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
If the tree were a straight line: a segment tree
On a line the villages are an array and a route is a range. Range maximum with point updates is the job of a segment tree. The simplest one is iterative: an array seg of length 2n, the values at the leaves seg[n … 2n − 1], and every inner box seg[i] = max(seg[2i], seg[2i + 1]).
update(p, x): set the leaf, then fix every box above it (p >>= 1): O(log n).query(l, r): move l and r up together; whenever l is a right child or r is a left child, that box is completely inside the range and is used: O(log n).
Episode 61 covers segment trees in depth (lazy propagation). Here it is just a tool.
Heavy children and heavy chains
- Sizes: a BFS gives an order with parents before children; going backwards (children first) gives every subtree size
sz[v]. - Heavy child: each village picks the child with the biggest subtree. The edge to it is heavy, every other child edge is light.
- Chains: heavy edges join into chains. Each chain is numbered consecutively: start at a chain head, walk down the heavy children giving positions 0, 1, 2, …, and push every light child as the head of a new chain.
For the sample, sizes are sz[1] = 10, sz[2] = 6, sz[4] = 4, sz[3] = 3, sz[6] = sz[9] = 2, the rest 1. The chains are 1–2–4–6–8, 3–9–10, 5 and 7, with positions:
| Position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| Village | 1 | 2 | 4 | 6 | 8 | 7 | 5 | 3 | 9 | 10 |
| head | 1 | 1 | 1 | 1 | 1 | 7 | 5 | 3 | 3 | 3 |
Printing every village's position and chain head for the sample confirms it (each chain is one block of positions):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
for (int v = 1; v <= n; v++) // where did every village go?
cout << "village " << v << ": pos " << pos[v] << ", head " << head[v] << "\n";
}
village 1: pos 0, head 1
village 2: pos 1, head 1
village 3: pos 7, head 3
village 4: pos 2, head 1
village 5: pos 6, head 5
village 6: pos 3, head 1
village 7: pos 5, head 7
village 8: pos 4, head 1
village 9: pos 8, head 3
village 10: pos 9, head 3
Why a path crosses at most log n chains
If c is a light child of v, then sz[c] ≤ sz[v] / 2: otherwise c would be bigger than every other child and would have been heavy. Going up from any village, every light edge at least doubles the subtree size, and sizes never exceed n, so at most log₂ n light edges lie on the way to the root. A path u–v is two such climbs, so it touches at most about 2 log₂ n + 1 chains.
Answering a route question
While u and v are on different chains, take the one whose chain head is deeper, answer the piece from its head down to it (one range), and jump to the parent of the head. When both are on one chain, the last piece is the range between their positions. For 7 → 10: the piece [7], then [3, 9, 10], then [1, 2, 4].
Bug 1: moving the deeper village
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[u] < dep[v]) swap(u, v); // move the deeper one
res = max(res, query(pos[head[u]], pos[u])); // u up to its chain head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v])); // same chain now
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) a[x] = y, update(pos[x], y); // village x: danger y
else cout << pathMax(x, y) << "\n";
}
}
9
9
8
7
For 8 → 7, village 8 is deeper, but its chain head is village 1. The code takes the whole range from 1 down to 8, which includes villages 1 and 2 that are not on the route (danger 9), and then jumps above the root. The deeper head is the one that can jump safely: its whole piece is on the route.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
res = max(res, query(pos[head[u]], pos[u])); // u up to its chain head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v])); // same chain now
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) a[x] = y, update(pos[x], y); // village x: danger y
else cout << pathMax(x, y) << "\n";
}
}
6
9
8
7
5
5
Bug 2: the first child as heavy
Calling the first child heavy still cuts the tree into chains, so every answer stays correct. But in the caterpillar every spine village lists its leaf first, so every spine edge becomes light and each route crosses 10^5 chains:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v]) heavy[v] = c; // the first child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
res = max(res, query(pos[head[u]], pos[u])); // u up to its chain head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v])); // same chain now
}
int main() {
n = 200000; // a long spine, one leaf on every spine village
for (int v = 1; v <= n; v++) a[v] = v % 1000;
for (int v = 2; v <= n; v++) {
par[v] = v % 2 == 0 ? v - 1 : v - 2; // leaf first, then the spine
ch[par[v]].push_back(v);
}
decompose();
ll sum = 0;
for (int i = 0; i < 200000; i++) // updates and deep queries
if (i % 2 == 0) update(pos[1 + i % n], i % 1000);
else sum += pathMax(199999 - 2 * (i % 1000), 2);
cout << sum << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
The biggest child is what makes the halving argument true:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
res = max(res, query(pos[head[u]], pos[u])); // u up to its chain head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v])); // same chain now
}
int main() {
n = 200000; // a long spine, one leaf on every spine village
for (int v = 1; v <= n; v++) a[v] = v % 1000;
for (int v = 2; v <= n; v++) {
par[v] = v % 2 == 0 ? v - 1 : v - 2; // leaf first, then the spine
ch[par[v]].push_back(v);
}
decompose();
ll sum = 0;
for (int i = 0; i < 200000; i++) // updates and deep queries
if (i % 2 == 0) update(pos[1 + i % n], i % 1000);
else sum += pathMax(199999 - 2 * (i % 1000), 2);
cout << sum << "\n";
}
99899249
Stress test against climbing
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
res = max(res, query(pos[head[u]], pos[u])); // u up to its chain head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v])); // same chain now
}
int climbMax(int u, int v) { // walk the route, one village at a time
int res = 0;
while (dep[u] > dep[v]) res = max(res, a[u]), u = par[u];
while (dep[v] > dep[u]) res = max(res, a[v]), v = par[v];
while (u != v) res = max({res, a[u], a[v]}), u = par[u], v = par[v];
return max(res, a[u]);
}
int main() {
mt19937 rng(55);
for (int t = 1; t <= 500; t++) {
n = rng() % 10 + 1;
for (int v = 1; v <= n; v++) ch[v].clear(), heavy[v] = 0, dep[v] = 0, a[v] = rng() % 100;
for (int v = 2; v <= n; v++) { // random tree
par[v] = rng() % (v - 1) + 1;
ch[par[v]].push_back(v);
}
decompose();
for (int k = 0; k < 20; k++) { // 20 random operations
int x = rng() % n + 1, y = rng() % n + 1;
if (rng() % 2) a[x] = y, update(pos[x], y);
else if (pathMax(x, y) != climbMax(x, y)) {
cout << "mismatch on test " << t;
return 0;
}
}
}
cout << "all 500 tests passed";
}
all 500 tests passed
Complexity vs the constraints
| Method | Preparation | Per question | Per update | Verdict at n, q = 2 · 10^5 |
|---|---|---|---|---|
| climb the route | O(n) | O(route), up to O(n) | O(1) | TLE |
| HLD with the first child as heavy | O(n) | up to O(n log n) | O(log n) | TLE on a caterpillar |
| HLD with the biggest child | O(n) + O(n) segment tree | O(log² n) ≈ 300 steps | O(log n) | accepted |
Memory: a few arrays of n ints plus a segment tree of 2n ints.
Common mistakes (and the real outputs)
| Mistake | What you see | Why | Fix |
|---|---|---|---|
| climbing the route | Time Limit Exceeded |
O(n) per question | HLD |
if (dep[u] < dep[v]) swap(u, v) |
9 9 8 7 (expected 6 9 8 7) |
the deeper village can sit on a shallow chain | compare dep[head[u]] and dep[head[v]] |
| first child as heavy | Time Limit Exceeded on a caterpillar |
no halving, n chains per path | the child with the biggest subtree |
update(x, y) instead of update(pos[x], y) |
wrong maxima | x is not its position | index by pos[x] |
last piece query(pos[v], pos[u]) with u shallower |
an empty range, answer 0 | the shallower village has the smaller position | swap so pos[u] ≤ pos[v] |
| recursive DFS for sizes on a spine of 10^5 | Runtime Error (stack overflow) | 10^5 nested calls | BFS order, backwards |
| values on roads but counting the top village | one extra road in the answer | the LCA's own road is not on the route | skip pos[lca] (homework 2) |
| segment tree of size n instead of 2n | memory corruption | leaves live at n … 2n − 1 | seg[2 * n] |
Mini project
Write an HLD class with build(parents), pathQuery(u, v), pointUpdate(v, x), lca(u, v) and subtreeQuery(v) (homework 3), parameterised by the operation (max, sum, min). Test it on a line, a star, a caterpillar, a complete binary tree and random trees against climbing, and time the caterpillar with both heavy-child rules to see the difference yourself.
Practice
These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).
1. Path sums with updates. Same input as Route Alert, but 2 x y prints the sum of the dangers on the route.
Solution
The same decomposition with a sum segment tree (long long, since sums reach 2 · 10^14).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001];
ll seg[400002];
vector<int> ch[200001];
void update(int p, ll x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = seg[p] + seg[p ^ 1];
}
ll query(int l, int r) { // sum of positions l..r
ll res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res += seg[l++];
if (r & 1) res += seg[--r];
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
ll pathSum(int u, int v) {
ll res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
res += query(pos[head[u]], pos[u]);
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return res + query(pos[u], pos[v]);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) a[x] = y, update(pos[x], y); // village x: danger y
else cout << pathSum(x, y) << "\n";
}
}
14
31
22
7
2. Values on roads, not villages. The input gives, for v = 2 … n, the parent p_v and the length w_v of the road from v up to p_v. 1 x y sets the road above x to y; 2 x y prints the longest road on the route from x to y (0 if x = y).
Solution
Store every road at its lower village. A chain piece from a head h down to u then includes the road above h, which is on the route. On the last chain, the shallower village's own road leads above the route, so skip it: query(pos[u] + 1, pos[v]).
#include <bits/stdc++.h>
using namespace std;
int n, w[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) {
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r (empty if l > r)
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1};
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) dep[c] = dep[bfs[i]] + 1, bfs.push_back(c);
for (int i = n - 1; i >= 0; i--) {
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c;
}
}
int cur = 0;
vector<int> st = {1};
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) {
head[v] = h, pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c);
}
}
for (int v = 2; v <= n; v++) update(pos[v], w[v]); // road v–par[v] lives at v
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v);
res = max(res, query(pos[head[u]], pos[u])); // includes the road above the head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u] + 1, pos[v])); // skip u: its road is not on the route
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 2; v <= n; v++) {
cin >> par[v] >> w[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) w[x] = y, update(pos[x], y); // the road from x up to its parent
else cout << pathMax(x, y) << "\n";
}
}
6
4
4
3. Subtree queries with the same positions. Route Alert plus a third operation 3 x: the highest danger in x's subtree.
Solution
Number the villages with a DFS that visits the heavy child first (push the light children, then push the heavy child last so it is popped next). Every chain is still consecutive, and every subtree is also one range, pos[x] … pos[x] + sz[x] − 1, exactly like the Euler tour of episode 54.
#include <bits/stdc++.h>
using namespace std;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) {
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) {
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1};
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) dep[c] = dep[bfs[i]] + 1, bfs.push_back(c);
for (int i = n - 1; i >= 0; i--) {
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c;
}
}
int cur = 0; // a DFS that visits the heavy child FIRST
vector<int> st = {1};
head[1] = 1;
while (!st.empty()) {
int v = st.back();
st.pop_back();
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) head[c] = c, st.push_back(c); // light: new chain
if (heavy[v]) head[heavy[v]] = head[v], st.push_back(heavy[v]); // heavy: popped next
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v);
res = max(res, query(pos[head[u]], pos[u]));
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v]));
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int type, x, y = 0;
cin >> type >> x;
if (type == 1) cin >> y, a[x] = y, update(pos[x], y);
else if (type == 2) cin >> y, cout << pathMax(x, y) << "\n";
else cout << query(pos[x], pos[x] + sz[x] - 1) << "\n"; // 3 x: max in x's subtree
}
}
7
8
6
5
4. The LCA using only head[] and par[]. Parent list input (no dangers); each question u v prints the LCA.
Solution
Move the deeper chain head up until both are on one chain; the LCA is then the shallower of the two. O(log n) per question with no jump table.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int lca(int u, int v) {
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
u = par[head[u]];
}
return dep[u] < dep[v] ? u : v; // same chain: the shallower one
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int u, v;
cin >> u >> v;
cout << lca(u, v) << "\n";
}
}
4
1
2
9
Quick quiz
A tree has about 10^6 villages. Going up from any village to the root, at most how many light edges can you cross?
sz[light child] <= sz[parent] / 2
A) 10 · B) 20 · C) 1000 · D) 10^6
Answer
B. Every light edge at least doubles the subtree size on the way up, and 2^20 ≈ 10^6, so at most about 20.
Interview questions
- What problem does heavy-light decomposition solve? Path queries with updates on a tree (max, sum, min, …) in O(log² n), by cutting the tree into chains that are ranges of one array.
- What is a heavy edge? The edge from a vertex to its child with the largest subtree. All other child edges are light.
- Why does any path cross O(log n) chains? A light child has at most half its parent's subtree, so each light edge on the way up at least doubles the size.
- How do you process a path query? While the endpoints are on different chains, query the piece of the one with the deeper chain head and jump to the parent of that head; finish with one range on the common chain.
- How do you handle values on edges? Store each edge at its lower vertex and exclude the LCA's position in the final range.
- Can HLD also answer subtree queries? Yes, if the DFS numbers the heavy child first: subtrees are contiguous ranges too.
- HLD vs binary lifting? Binary lifting gives LCA and k-th ancestor in O(log n) but no updates on path aggregates; HLD supports point (and with lazy segment trees, range) updates along paths.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Path (route) | The unique sequence of vertices between two vertices of a tree | 8, 6, 4, 7 |
| Path query | A question about all values on a path | the highest danger |
| Point update | Changing one value | 1 1 0 |
| Segment tree | A tree of boxes over an array; each box stores the result for its range | seg[2n] |
| Range maximum query | The largest value in a range of an array | query(l, r) |
Subtree size sz[v] |
Vertices in v's subtree | sz[2] = 6 |
| Heavy child | The child with the biggest subtree | heavy[2] = 4 |
| Heavy edge / light edge | The edge to the heavy child / to any other child | 1–2 heavy, 1–3 light |
| Heavy chain | A maximal path of heavy edges | 1–2–4–6–8 |
Chain head head[v] |
The top vertex of v's chain | head[10] = 3 |
Position pos[v] |
v's index in the array the segment tree works on | pos[3] = 7 |
| Decomposition | Cutting a tree into pieces with useful structure | the chains |
| Caterpillar | A path (spine) with leaves hanging off it | the maximum test |
| Spine | The long central path of a caterpillar | 1, 3, 5, … |
| BFS order | Parents before children; backwards gives children before parents | sizes |
| LCA | The deepest common ancestor | homework 4 |
| Stress test | Comparing a fast solution with a slow, surely-correct one on many random inputs | all 500 tests passed |
| O(log² n) | log n times log n | log n chains × log n per range |
| Time Limit Exceeded (TLE) | Too slow | climbing, first-child heavy |
| Wrong Answer (WA) | A wrong output | 9 9 8 7 |
Summary
- A segment tree answers range max with point updates on an array in O(log n).
- Heavy child = the child with the biggest subtree; heavy edges form chains; number each chain consecutively.
- A light child has at most half its parent's subtree, so any path crosses O(log n) chains.
- Path query: repeatedly take the endpoint with the deeper chain head, query its piece, jump above the head; finish on the shared chain. Moving the deeper village prints
9 9 8 7. - The first child as heavy is correct but TLE on a caterpillar; the biggest child is accepted.
- Query O(log² n), update O(log n), preparation O(n).
Solutions in C++, Java and Python
Problem H1 · Route Alert
C++
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, a[200001], par[200001], dep[200001], sz[200001];
int heavy[200001], head[200001], pos[200001], seg[400002];
vector<int> ch[200001];
void update(int p, int x) { // segment tree: set position p
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = max(seg[p], seg[p ^ 1]);
}
int query(int l, int r) { // max of positions l..r
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if (l & 1) res = max(res, seg[l++]);
if (r & 1) res = max(res, seg[--r]);
}
return res;
}
void decompose() {
vector<int> bfs = {1}; // parents before children
for (int i = 0; i < (int)bfs.size(); i++)
for (int c : ch[bfs[i]]) {
dep[c] = dep[bfs[i]] + 1;
bfs.push_back(c);
}
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c : ch[v]) {
sz[v] += sz[c];
if (!heavy[v] || sz[c] > sz[heavy[v]]) heavy[v] = c; // the biggest child
}
}
int cur = 0;
vector<int> st = {1}; // chain heads still to number
while (!st.empty()) {
int h = st.back();
st.pop_back();
for (int v = h; v; v = heavy[v]) { // walk down one heavy chain
head[v] = h;
pos[v] = cur++;
for (int c : ch[v]) if (c != heavy[v]) st.push_back(c); // light child: new chain
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) swap(u, v); // move the deeper chain head
res = max(res, query(pos[head[u]], pos[u])); // u up to its chain head
u = par[head[u]];
}
if (dep[u] > dep[v]) swap(u, v);
return max(res, query(pos[u], pos[v])); // same chain now
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> n >> q;
for (int v = 1; v <= n; v++) cin >> a[v];
for (int v = 2; v <= n; v++) {
cin >> par[v];
ch[par[v]].push_back(v);
}
decompose();
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) a[x] = y, update(pos[x], y); // village x: danger y
else cout << pathMax(x, y) << "\n";
}
}
Java
import java.io.*;
import java.util.*;
public class Main {
static int n;
static int[] a, par, dep, sz, heavy, head, pos, seg, chHead, chNext;
static void update(int p, int x) {
for (seg[p += n] = x; p > 1; p >>= 1) seg[p >> 1] = Math.max(seg[p], seg[p ^ 1]);
}
static int query(int l, int r) {
int res = 0;
for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) res = Math.max(res, seg[l++]);
if ((r & 1) == 1) res = Math.max(res, seg[--r]);
}
return res;
}
static void decompose() {
int[] bfs = new int[n];
int len = 0;
bfs[len++] = 1;
for (int i = 0; i < len; i++)
for (int c = chHead[bfs[i]]; c != 0; c = chNext[c]) { dep[c] = dep[bfs[i]] + 1; bfs[len++] = c; }
for (int i = n - 1; i >= 0; i--) { // children before parents
int v = bfs[i];
sz[v] = 1;
for (int c = chHead[v]; c != 0; c = chNext[c]) {
sz[v] += sz[c];
if (heavy[v] == 0 || sz[c] > sz[heavy[v]]) heavy[v] = c;
}
}
int cur = 0, top = 0;
int[] st = new int[n + 1];
st[top++] = 1;
while (top > 0) {
int h = st[--top];
for (int v = h; v != 0; v = heavy[v]) {
head[v] = h;
pos[v] = cur++;
for (int c = chHead[v]; c != 0; c = chNext[c]) if (c != heavy[v]) st[top++] = c;
}
}
for (int v = 1; v <= n; v++) update(pos[v], a[v]);
}
static int pathMax(int u, int v) {
int res = 0;
while (head[u] != head[v]) {
if (dep[head[u]] < dep[head[v]]) { int t = u; u = v; v = t; }
res = Math.max(res, query(pos[head[u]], pos[u]));
u = par[head[u]];
}
if (dep[u] > dep[v]) { int t = u; u = v; v = t; }
return Math.max(res, query(pos[u], pos[v]));
}
public static void main(String[] args) throws IOException {
DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
n = nextInt(in);
int q = nextInt(in);
a = new int[n + 1]; par = new int[n + 1]; dep = new int[n + 1]; sz = new int[n + 1];
heavy = new int[n + 1]; head = new int[n + 1]; pos = new int[n + 1]; seg = new int[2 * n + 2];
chHead = new int[n + 1]; chNext = new int[n + 1];
for (int v = 1; v <= n; v++) a[v] = nextInt(in);
for (int v = 2; v <= n; v++) {
par[v] = nextInt(in);
chNext[v] = chHead[par[v]];
chHead[par[v]] = v;
}
decompose();
StringBuilder sb = new StringBuilder();
while (q-- > 0) {
int type = nextInt(in), x = nextInt(in), y = nextInt(in);
if (type == 1) { a[x] = y; update(pos[x], y); }
else sb.append(pathMax(x, y)).append('\n');
}
System.out.print(sb);
}
static int nextInt(DataInputStream in) throws IOException {
int r = 0, b = in.read();
while (b < '0') b = in.read();
while (b >= '0') { r = r * 10 + b - '0'; b = in.read(); }
return r;
}
}
6
9
8
7
Python
import sys
def main():
data = sys.stdin.buffer.read().split()
n, q = int(data[0]), int(data[1])
a = [0] + [int(x) for x in data[2:n + 2]]
par = [0, 0] + [int(x) for x in data[n + 2:2 * n + 1]]
ch = [[] for _ in range(n + 1)]
for v in range(2, n + 1):
ch[par[v]].append(v)
dep = [0] * (n + 1)
bfs = [1]
for v in bfs: # parents before children
for c in ch[v]:
dep[c] = dep[v] + 1
bfs.append(c)
sz, heavy = [1] * (n + 1), [0] * (n + 1)
for v in reversed(bfs): # children before parents
for c in ch[v]:
sz[v] += sz[c]
if heavy[v] == 0 or sz[c] > sz[heavy[v]]:
heavy[v] = c
head, pos = [0] * (n + 1), [0] * (n + 1)
cur, st = 0, [1]
while st:
h = st.pop()
v = h
while v: # walk down one heavy chain
head[v], pos[v] = h, cur
cur += 1
st.extend(c for c in ch[v] if c != heavy[v])
v = heavy[v]
seg = [0] * (2 * n)
for v in range(1, n + 1):
seg[pos[v] + n] = a[v]
for p in range(n - 1, 0, -1):
seg[p] = max(seg[2 * p], seg[2 * p + 1])
def update(p, x):
p += n
seg[p] = x
while p > 1:
p >>= 1
seg[p] = max(seg[2 * p], seg[2 * p + 1])
def query(l, r):
res, l, r = 0, l + n, r + n + 1
while l < r:
if l & 1:
res = max(res, seg[l]); l += 1
if r & 1:
r -= 1; res = max(res, seg[r])
l >>= 1; r >>= 1
return res
def path_max(u, v):
res = 0
while head[u] != head[v]:
if dep[head[u]] < dep[head[v]]:
u, v = v, u
res = max(res, query(pos[head[u]], pos[u]))
u = par[head[u]]
if dep[u] > dep[v]:
u, v = v, u
return max(res, query(pos[u], pos[v]))
out, p = [], 2 * n + 1
for _ in range(q):
t, x, y = data[p], int(data[p + 1]), int(data[p + 2])
p += 3
if t == b"1":
a[x] = y
update(pos[x], y)
else:
out.append(path_max(x, y))
print("\n".join(map(str, out)))
main()
6
9
8
7
With 2 · 10^5 operations of O(log² n) each, CPython can be slow; submit with PyPy if the judge offers it.