SyntaxPilot
Courses/Competitive Programming/Lesson 56
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 56 of 90

Centroid decomposition

queued

These are the notes for Competitive Programming episode 56. A centroid of a tree is a vertex whose removal leaves no piece with more than half of the vertices. Centroid decomposition removes a centroid, handles every path through it, and repeats inside each piece: pieces at least halve, so there are at most log₂ n levels. Exactly K Apart counts pairs of villages exactly K roads apart: a BFS from every village is correct but Time Limit Exceeded at n = 2 · 10^5. Counting the pairs through the centroid branch by branch, counting before adding, is O(n log n); adding a branch before counting it pairs villages of the same branch (and a village with itself) and prints 13 where 7 is right. Cutting at any village is still correct but TLE on a line. Nearest Ration Shop keeps, for every village, its distance to each centroid above it; INF = INT_MAX overflows and prints -2147483648 where -1 is right. 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 district officer splits the district for a survey. They pick the middle village: closing it leaves no piece with more than half of the villages. Now any route between two villages either passes through the middle village or stays completely inside one piece, because the pieces only touch through it. The officer counts the routes through the middle village, and hands every piece to its own officer, who picks that piece's middle and does the same. Pieces at least halve every time, so after about log₂ n rounds every piece is a single village.

Problem D1 · Exactly K Apart

(Written for this course, in the style of a Codeforces Div. 2 F / Div. 1 D problem.)

A tree of n villages; every road is 1 km. Count the unordered pairs {u, v} whose route is exactly K km long.

  • Input: n K (1 ≤ n ≤ 2 · 10^5, 1 ≤ K ≤ n), then n − 1 lines a b.
  • Output: the number of pairs (up to about n² / 2, so long long).
7 2
1 2
2 3
3 4
2 5
5 6
5 7
   1           6
    \         /
     2 ----- 5
    /         \
   3           7
   |
   4

With K = 2 the pairs are {1, 3}, {1, 5}, {3, 5}, {2, 4}, {2, 6}, {2, 7} and {6, 7}: 7. With K = 3 the answer is 6.

The obvious attempt: a BFS from every village (TLE)

bfs(s, from, d0) collects every village reachable from s, with its distance, without crossing the village from (and without entering removed villages, used later). Running it from every village sees every pair twice.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll pairs = 0;
    for (int s = 1; s <= n; s++) {           // a BFS from every village
        bfs(s, 0, 0);
        for (auto [v, d] : got) if (d == K) pairs++;
    }
    cout << pairs / 2 << "\n";             // each pair seen from both ends
}
7
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int main() {
    n = 200000, K = 1000;                  // one long line of villages
    for (int v = 1; v < n; v++) {
        g[v].push_back(v + 1);
        g[v + 1].push_back(v);
    }
    ll pairs = 0;
    for (int s = 1; s <= n; s++) {           // a BFS from every village
        bfs(s, 0, 0);
        for (auto [v, d] : got) if (d == K) pairs++;
    }
    cout << pairs / 2 << "\n";             // each pair seen from both ends
}
Time Limit Exceeded (stopped after 8 seconds)

The centroid

Root the current piece anywhere and compute subtree sizes (BFS order backwards). Start at the root and, while some child's subtree has more than half of the piece, step into it. When no child is bigger than half, stop: the part "above" the current village is also smaller than half (because we only stepped into a child bigger than half). That village is a centroid. In the sample, removing village 2 leaves pieces {1}, {3, 4} and {5, 6, 7}, all of size ≤ 3.5.

Every tree has a centroid, and one walk finds it in O(size of the piece).

Counting the pairs through c

A route through the centroid c joins two villages in different branches of c (or c and one other village). If they are at distances d1 and d2 from c, they are d1 + d2 apart.

Keep cnt[d] = number of villages already seen at distance d from c, with cnt[0] = 1 for c itself. For each branch of c:

  1. BFS the branch (distances start at 1);
  2. count: for every village at distance d ≤ K, add cnt[K − d];
  3. then add the branch's distances into cnt.

Afterwards clear cnt[0 … top] (only what was used) and put every branch on the to-do list. The list replaces recursion.

The bug: adding before counting

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll ans = 0;
    vector<int> todo = {1};                // pieces still to cut
    while (!todo.empty()) {
        int c = centroid(todo.back());       // cut at the middle
        todo.pop_back();
        removed[c] = true;
        cnt[0] = 1;                          // c itself, distance 0
        int top = 0;
        for (int u : g[c]) if (!removed[u]) {   // one branch at a time
            bfs(u, c, 1);
            for (auto [v, d] : got) cnt[d]++, top = max(top, d);    // add this branch
            for (auto [v, d] : got) if (d <= K) ans += cnt[K - d];   // pairs through c
        }
        fill(cnt, cnt + top + 1, 0);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
13

Adding a branch first lets each of its villages pair with villages of the same branch, whose real route does not go through c, and even with itself when 2d = K. With K = 2, every village one road from a centroid was paired with itself.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll ans = 0;
    vector<int> todo = {1};                // pieces still to cut
    while (!todo.empty()) {
        int c = centroid(todo.back());       // cut at the middle
        todo.pop_back();
        removed[c] = true;
        cnt[0] = 1;                          // c itself, distance 0
        int top = 0;
        for (int u : g[c]) if (!removed[u]) {   // one branch at a time
            bfs(u, c, 1);
            for (auto [v, d] : got) if (d <= K) ans += cnt[K - d];   // pairs through c
            for (auto [v, d] : got) cnt[d]++, top = max(top, d);    // then add this branch
        }
        fill(cnt, cnt + top + 1, 0);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
7
6
0

Why the middle, and not any village

Cutting at the first village of each piece still counts every route exactly once, so it is still correct. But on a line, cutting at the end leaves a piece of n − 1 villages, then n − 2, …: n levels, O(n²).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

int main() {
    n = 200000, K = 1000;                  // one long line of villages
    for (int v = 1; v < n; v++) {
        g[v].push_back(v + 1);
        g[v + 1].push_back(v);
    }
    ll ans = 0;
    vector<int> todo = {1};                // pieces still to cut
    while (!todo.empty()) {
        int c = todo.back();                 // cut at any village
        todo.pop_back();
        removed[c] = true;
        cnt[0] = 1;                          // c itself, distance 0
        int top = 0;
        for (int u : g[c]) if (!removed[u]) {   // one branch at a time
            bfs(u, c, 1);
            for (auto [v, d] : got) if (d <= K) ans += cnt[K - d];   // pairs through c
            for (auto [v, d] : got) cnt[d]++, top = max(top, d);    // then add this branch
        }
        fill(cnt, cnt + top + 1, 0);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

int main() {
    n = 200000, K = 1000;                  // one long line of villages
    for (int v = 1; v < n; v++) {
        g[v].push_back(v + 1);
        g[v + 1].push_back(v);
    }
    ll ans = 0;
    vector<int> todo = {1};                // pieces still to cut
    while (!todo.empty()) {
        int c = centroid(todo.back());       // cut at the middle
        todo.pop_back();
        removed[c] = true;
        cnt[0] = 1;                          // c itself, distance 0
        int top = 0;
        for (int u : g[c]) if (!removed[u]) {   // one branch at a time
            bfs(u, c, 1);
            for (auto [v, d] : got) if (d <= K) ans += cnt[K - d];   // pairs through c
            for (auto [v, d] : got) cnt[d]++, top = max(top, d);    // then add this branch
        }
        fill(cnt, cnt + top + 1, 0);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
199000

On a line, the pairs exactly K apart are (1, K + 1), (2, K + 2), …: n − K = 199 000.

Stress test against the brute force

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

ll brute() {
    ll pairs = 0;
    for (int s = 1; s <= n; s++) {
        bfs(s, 0, 0);
        for (auto [v, d] : got) if (d == K) pairs++;
    }
    return pairs / 2;
}

ll fast() {
    ll ans = 0;
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        removed[c] = true;
        cnt[0] = 1;
        int top = 0;
        for (int u : g[c]) if (!removed[u]) {
            bfs(u, c, 1);
            for (auto [v, d] : got) if (d <= K) ans += cnt[K - d];   // pairs through c
            for (auto [v, d] : got) cnt[d]++, top = max(top, d);    // then add this branch
        }
        fill(cnt, cnt + top + 1, 0);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    return ans;
}

int main() {
    mt19937 rng(56);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 10 + 1, K = rng() % n + 1;
        for (int v = 1; v <= n; v++) g[v].clear(), removed[v] = false;
        for (int v = 2; v <= n; v++) {       // random tree
            int p = rng() % (v - 1) + 1;
            g[v].push_back(p);
            g[p].push_back(v);
        }
        ll slow = brute();
        if (fast() != slow) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem D2 · Nearest Ration Shop

(Written for this course.)

The same kind of tree (n villages, 1 km roads). Ration shops open one by one. Process q operations: 1 v opens a shop at v; 2 v prints the distance from v to the nearest open shop, or −1 if none is open. n, q ≤ 2 · 10^5.

7 7
1 2
2 3
3 4
2 5
5 6
5 7
2 4
1 6
2 4
1 3
2 4
2 7
2 6

Distances to the centroids above

Decompose the tree once. For two villages v and s, look at the first centroid c that separated them, i.e. the first one chosen in a piece containing both. Their route passes through c, so dist(v, s) = dist(v, c) + dist(c, s). For every other centroid c' whose piece contains both, dist(v, c') + dist(c', s) ≥ dist(v, s). So

nearest(v) = min over the centroids c above v of  best[c] + dist(v, c)
best[c]    = min over the open shops s in c's piece of  dist(s, c)

Every village lies in at most log₂ n + 1 pieces, so it keeps at most about 18 pairs (centroid, distance); one BFS per piece, before removing its centroid, fills them. Opening a shop updates best for its ≤ 18 centroids; a question looks at ≤ 18 centroids.

The bug: an INF that overflows

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, sz[200001], par[200001], best[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;
vector<pair<int, int>> anc[200001];       // (centroid above v, distance)
const int INF = INT_MAX;

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

void build() {
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        bfs(c, 0, 0);                        // c's whole piece
        for (auto [v, d] : got) anc[v].push_back({c, d});
        best[c] = INF;
        removed[c] = true;
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
}

void openShop(int v) {
    for (auto [c, d] : anc[v]) best[c] = min(best[c], d);
}
int nearest(int v) {
    int res = INF;
    for (auto [c, d] : anc[v]) res = min(res, best[c] + d);   // via centroid c
    return res >= INF ? -1 : res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    build();
    while (q--) {
        int type, v;
        cin >> type >> v;
        if (type == 1) openShop(v);
        else cout << nearest(v) << "\n";
    }
}
-2147483648
-2147483648
1
2
0

Before any shop opens, best[c] + d is INT_MAX + d, which overflows int (formally undefined behaviour; here it wrapped to a huge negative number), and min picks it. An INF with room to add, 10^9, fixes it.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, sz[200001], par[200001], best[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;
vector<pair<int, int>> anc[200001];       // (centroid above v, distance)
const int INF = 1e9;                       // INF + distance still fits in int

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

void build() {
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        bfs(c, 0, 0);                        // c's whole piece
        for (auto [v, d] : got) anc[v].push_back({c, d});
        best[c] = INF;
        removed[c] = true;
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
}

void openShop(int v) {
    for (auto [c, d] : anc[v]) best[c] = min(best[c], d);
}
int nearest(int v) {
    int res = INF;
    for (auto [c, d] : anc[v]) res = min(res, best[c] + d);   // via centroid c
    return res >= INF ? -1 : res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    build();
    while (q--) {
        int type, v;
        cin >> type >> v;
        if (type == 1) openShop(v);
        else cout << nearest(v) << "\n";
    }
}
-1
4
1
2
0

On a line with one shop at village 1 and 2 · 10^5 questions from the far end, a BFS per question is too slow:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, par[200001];
vector<int> g[200001];
bool removed[200001], shop[200001];
vector<pair<int, int>> got;

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int nearest(int v) {                       // BFS until the first shop
    bfs(v, 0, 0);
    for (auto [u, d] : got) if (shop[u]) return d;
    return -1;
}

int main() {
    n = 200000;                            // one long line, a shop at village 1
    for (int v = 1; v < n; v++) {
        g[v].push_back(v + 1);
        g[v + 1].push_back(v);
    }
    shop[1] = true;
    ll sum = 0;
    for (int i = 0; i < 200000; i++) sum += nearest(n - i % 1000);
    cout << sum << "\n";
}
Time Limit Exceeded (stopped after 8 seconds)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, sz[200001], par[200001], best[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;
vector<pair<int, int>> anc[200001];       // (centroid above v, distance)
const int INF = 1e9;                       // INF + distance still fits in int

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

void build() {
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        bfs(c, 0, 0);                        // c's whole piece
        for (auto [v, d] : got) anc[v].push_back({c, d});
        best[c] = INF;
        removed[c] = true;
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
}

void openShop(int v) {
    for (auto [c, d] : anc[v]) best[c] = min(best[c], d);
}
int nearest(int v) {
    int res = INF;
    for (auto [c, d] : anc[v]) res = min(res, best[c] + d);   // via centroid c
    return res >= INF ? -1 : res;
}

int main() {
    n = 200000;                            // one long line, a shop at village 1
    for (int v = 1; v < n; v++) {
        g[v].push_back(v + 1);
        g[v + 1].push_back(v);
    }
    build();
    openShop(1);
    ll sum = 0;
    for (int i = 0; i < 200000; i++) sum += nearest(n - i % 1000);
    cout << sum << "\n";
}
39899900000

Complexity vs the constraints

Method Time Memory Verdict at n = 2 · 10^5
a BFS from every village O(n²) O(n) TLE
cut at any village O(n²) on a line O(n) TLE
centroid decomposition, count with cnt[] O(n log n) O(n) accepted
clearing all of cnt[] at every centroid O(n²) O(n) TLE
shops: build O(n log n) O(n log n) pairs ≈ 3.6 · 10^6 accepted
shops: per operation O(log n) accepted
a BFS per shop question O(n) per question O(n) TLE

Common mistakes (and the real outputs)

Mistake What you see Why Fix
BFS from every village Time Limit Exceeded O(n²) centroid decomposition
adding a branch to cnt before counting it 13 (expected 7) pairs inside one branch, a village with itself count, then add
cutting at any village Time Limit Exceeded on a line n levels cut at the centroid
INF = INT_MAX and best[c] + d -2147483648 (expected -1) int overflow INF = 1e9
memset(cnt, 0, sizeof cnt) at every centroid Time Limit Exceeded O(n) per centroid clear only cnt[0 … top]
forgetting cnt[0] = 1 pairs with c itself are missed c is at distance 0 set it at every centroid
BFS crossing removed villages double counting, wrong answers pieces leak into each other skip removed[u]
recursive decomposition plus recursive DFS Runtime Error on deep trees the size DFS can be 2 · 10^5 deep BFS for sizes, a to-do list
int answer wrapped count up to ≈ 2 · 10^10 long long

Mini project

Write a reusable centroid decomposition that returns, for every centroid, its parent in the centroid tree and its level, plus each village's list of (centroid, distance). On top of it implement countExactlyK, countAtMostK (homework 1) and the shop structure with open and close (homework 3). Test on a line, a star, a caterpillar and random trees; check the small ones against BFS brute forces and check that the centroid tree's depth never exceeds log₂ n + 1.

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. Count pairs at distance at most K. Same input as Exactly K Apart.

Solution

At each centroid, collect all distances (c itself at 0). Count the pairs with d1 + d2 ≤ K by sorting and two pointers, then subtract the same count inside each branch (those pairs don't go through c). O(n log² n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

ll countPairs(vector<int>& d) {           // pairs (i < j) with d[i] + d[j] <= K
    sort(d.begin(), d.end());
    ll res = 0;
    int i = 0, j = (int)d.size() - 1;
    while (i < j) {
        if (d[i] + d[j] <= K) res += j - i, i++;
        else j--;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll ans = 0;
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        removed[c] = true;
        vector<int> all = {0};                    // c itself
        for (int u : g[c]) if (!removed[u]) {
            bfs(u, c, 1);
            vector<int> br;
            for (auto [v, d] : got) br.push_back(d);
            ans -= countPairs(br);                // pairs inside one branch don't go through c
            all.insert(all.end(), br.begin(), br.end());
        }
        ans += countPairs(all);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
13

(For the sample with K = 2: 6 pairs at distance 1 and 7 at distance 2.)

2. Weighted roads. Roads have lengths 1 ≤ w ≤ 10^9 (input lines a b w). Count the pairs whose route is exactly K long (K ≤ 10^18).

Solution

Distances no longer fit an array index, so cnt becomes a map<long long, int>. The rest is the same: count, then add. O(n log² n).

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, sz[200001], par[200001];
ll K;
vector<pair<int, int>> g[200001];             // (neighbour, length)
bool removed[200001];
vector<pair<int, ll>> got;

void bfs(int s, int from, ll d0) {
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (auto [u, w] : g[v])
            if (u != par[v] && !removed[u]) par[u] = v, got.push_back({u, d + w});
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {
        int v = got[i].first;
        sz[v] = 1;
        for (auto [u, w] : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {
        int next = 0;
        for (auto [u, w] : g[c]) if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 0; i < n - 1; i++) {
        int a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    ll ans = 0;
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        removed[c] = true;
        map<ll, int> cnt = {{0, 1}};              // distances can be big: a map, not an array
        for (auto [u, w] : g[c]) if (!removed[u]) {
            bfs(u, c, w);
            for (auto [v, d] : got) {
                auto it = cnt.find(K - d);
                if (it != cnt.end()) ans += it->second;
            }
            for (auto [v, d] : got) if (d <= K) cnt[d]++;
        }
        for (auto [u, w] : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
3

(The episode 52 tree with K = 6: {3, 4}, {4, 5} and {6, 4}.)

3. Shops can close too. Nearest Ration Shop plus 3 v: the shop at v closes (it is open).

Solution

A single minimum per centroid cannot "forget" a closed shop. Keep a multiset of distances at each centroid: open inserts, close erases one copy, and the nearest is the smallest element. O(log² n) per operation.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, sz[200001], par[200001];
multiset<int> best[200001];             // distances to the OPEN shops, per centroid
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;
vector<pair<int, int>> anc[200001];       // (centroid above v, distance)
const int INF = 1e9;                       // INF + distance still fits in int

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

void build() {
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        bfs(c, 0, 0);                        // c's whole piece
        for (auto [v, d] : got) anc[v].push_back({c, d});
        removed[c] = true;
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
}

void openShop(int v) {
    for (auto [c, d] : anc[v]) best[c].insert(d);
}
void closeShop(int v) {
    for (auto [c, d] : anc[v]) best[c].erase(best[c].find(d));   // remove ONE copy
}
int nearest(int v) {
    int res = INF;
    for (auto [c, d] : anc[v])
        if (!best[c].empty()) res = min(res, *best[c].begin() + d);
    return res >= INF ? -1 : res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    build();
    while (q--) {
        int type, v;
        cin >> type >> v;
        if (type == 1) openShop(v);
        else if (type == 3) closeShop(v);
        else cout << nearest(v) << "\n";
    }
}
1
4
-1
-1

4. The longest route with at most K special villages. Each village is special (1) or not (0). Print the largest number of roads on a route that contains at most K special villages (both ends included), or −1 if even a single village is too many.

Solution

At centroid c, every village x of a branch has a depth d(x) and a count k(x) of special villages from x up to (not including) c. Two villages of different branches combine when k(x) + k(y) + special(c) ≤ K, giving d(x) + d(y). A Fenwick tree of maxima indexed by k answers "the deepest earlier village with at most k specials" in O(log n); c itself is (k = 0, d = 0). Count, then add, branch by branch; reset only the touched cells. O(n log² n). (Checked against a brute force on 300 random trees.)

#include <bits/stdc++.h>
using namespace std;

int n, K, sz[200001], par[200001], fen[200002];
vector<int> g[200001];
bool removed[200001], special[200001];
vector<array<int, 3>> got;                    // (village, distance, special villages after c)

void bfs(int s, int from) {
    got = {{s, 1, special[s]}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d, k] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) par[u] = v, got.push_back({u, d + 1, k + special[u]});
    }
}

int centroid(int s) {
    got = {{s, 0, 0}};
    par[s] = 0;
    for (int i = 0; i < (int)got.size(); i++) {
        int v = got[i][0];
        for (int u : g[v]) if (u != par[v] && !removed[u]) par[u] = v, got.push_back({u, 0, 0});
    }
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {
        int v = got[i][0];
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {
        int next = 0;
        for (int u : g[c]) if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

// Fenwick tree of maxima over "special count + 1": the longest branch with at most k specials
vector<int> touched;
void put(int i, int d) { for (i++; i <= n + 1; i += i & -i) if (d > fen[i]) fen[i] = d, touched.push_back(i); }
int best(int i) { int r = -1; for (i++; i > 0; i -= i & -i) r = max(r, fen[i]); return r; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int v = 1; v <= n; v++) { int s; cin >> s; special[v] = s; }
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    fill(fen, fen + n + 2, -1);
    int ans = -1;
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        removed[c] = true;
        int sc = special[c];
        if (sc <= K) ans = max(ans, 0), put(0, 0);       // the route of c alone
        for (int u : g[c]) if (!removed[u]) {
            bfs(u, c);
            for (auto [v, d, k] : got)                  // pair with earlier branches (or c)
                if (k + sc <= K) {
                    int b = best(K - sc - k);
                    if (b >= 0) ans = max(ans, d + b);
                }
            for (auto [v, d, k] : got) if (k + sc <= K) put(k, d);
        }
        for (int i : touched) fen[i] = -1;
        touched.clear();
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}
4

Quick quiz

A straight line of 15 villages. How many levels of centroid cuts does it take?

15 → 7 + 7 → 3 + 3 → 1 + 1

A) 2 · B) 4 · C) 8 · D) 15

Answer

B. The middle, village 8, leaves two lines of 7; their middles leave lines of 3; then single villages. 4 levels (⌊log₂ 15⌋ + 1).

Interview questions

  1. What is the centroid of a tree? A vertex whose removal leaves components of size at most n / 2. Every tree has one (or two adjacent ones).
  2. How do you find it? Compute subtree sizes from any root, then repeatedly step into a child with size > n / 2.
  3. Why is centroid decomposition O(n log n)? Each piece is at most half its parent piece, so a vertex appears in at most log₂ n + 1 pieces, and each level does linear work.
  4. How do you count paths of length K? At each centroid, combine distances from different branches with a counting array, counting before adding each branch.
  5. What is the centroid tree? The tree where each centroid's parent is the centroid of the piece it was found in; its depth is O(log n), and the path between two vertices passes through their LCA in the centroid tree.
  6. How do you answer "nearest marked vertex" queries? Store dist(v, c) for every centroid ancestor c; marking updates best[c], querying takes min best[c] + dist(v, c).
  7. Centroid vs heavy-light decomposition? HLD answers questions about one given path (with updates); centroid decomposition aggregates over all paths or answers nearest-type queries.

Glossary

Term Meaning Example
Distance The number of roads on the route dist(6, 7) = 2
Pair {u, v} Two different villages, order not counted {1, 3}
Centroid A vertex whose removal leaves pieces of size ≤ n / 2 village 2
Piece (component) A connected part left after removing vertices {5, 6, 7}
Branch A piece hanging off the centroid through one neighbour the branch of 5
Centroid decomposition Remove a centroid, handle paths through it, repeat in each piece D1, D2
Centroid tree The tree of centroids: each one's parent is the centroid of its piece depth ≤ log₂ n + 1
Level How many cuts above a centroid 4 levels for a line of 15
cnt[d] Villages seen so far at distance d from the centroid cnt[0] = 1
Count, then add Pair a branch with earlier branches before adding it the D1 fix
To-do list A stack of pieces still to cut, replacing recursion vector<int> todo
removed[] Villages already used as centroids; BFS never crosses them removed[c] = true
INF A value larger than any real answer 1e9
Integer overflow A result too big for its type INT_MAX + 1
Undefined behaviour Code whose result C++ does not define, such as signed overflow -2147483648
Multiset A sorted container that keeps duplicates homework 3
Two pointers Scanning a sorted array from both ends homework 1
Fenwick tree of maxima A Fenwick tree storing prefix maxima homework 4
Caterpillar, line, star Common test shapes: a path with leaves, a path, one hub test trees
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
O(n log n) n times log n the decomposition
Time Limit Exceeded (TLE) Too slow BFS from everyone
Wrong Answer (WA) A wrong output 13, -2147483648
Functional graph A graph where every vertex has exactly one outgoing edge next episode

Summary

  • A centroid leaves pieces of size ≤ n / 2; find it by stepping into any child bigger than half.
  • Every route passes through the centroid or stays inside one piece; recurse with a to-do list.
  • Pieces halve: log n levels, O(n log n) in total.
  • Count pairs through c branch by branch: count, then add; adding first prints 13 instead of 7.
  • Cutting at any village is correct but O(n²) on a line.
  • Each village keeps its distance to ≤ log n + 1 centroids above it: nearest open shop = min best[c] + dist(v, c).
  • INF = INT_MAX overflows when you add to it (-2147483648); use 10^9.

Solutions in C++, Java and Python

Problem D1 · Exactly K Apart

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, K, sz[200001], par[200001], cnt[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;               // (village, distance) from the last BFS

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> K;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    ll ans = 0;
    vector<int> todo = {1};                // pieces still to cut
    while (!todo.empty()) {
        int c = centroid(todo.back());       // cut at the middle
        todo.pop_back();
        removed[c] = true;
        cnt[0] = 1;                          // c itself, distance 0
        int top = 0;
        for (int u : g[c]) if (!removed[u]) {   // one branch at a time
            bfs(u, c, 1);
            for (auto [v, d] : got) if (d <= K) ans += cnt[K - d];   // pairs through c
            for (auto [v, d] : got) cnt[d]++, top = max(top, d);    // then add this branch
        }
        fill(cnt, cnt + top + 1, 0);
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
    cout << ans << "\n";
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] head, nxt, to, sz, par;
    static boolean[] removed;
    static int[] gotV, gotD;                      // the last BFS: villages and distances
    static int gotN;

    static void bfs(int s, int from, int d0) {
        gotN = 0;
        gotV[gotN] = s; gotD[gotN++] = d0;
        par[s] = from;
        for (int i = 0; i < gotN; i++) {
            int v = gotV[i];
            for (int e = head[v]; e != -1; e = nxt[e]) {
                int u = to[e];
                if (u != par[v] && !removed[u]) { par[u] = v; gotV[gotN] = u; gotD[gotN++] = gotD[i] + 1; }
            }
        }
    }
    static int centroid(int s) {
        bfs(s, 0, 0);
        int tot = gotN;
        for (int i = tot - 1; i >= 0; i--) {
            int v = gotV[i];
            sz[v] = 1;
            for (int e = head[v]; e != -1; e = nxt[e]) { int u = to[e]; if (u != par[v] && !removed[u]) sz[v] += sz[u]; }
        }
        int c = s;
        while (true) {
            int next = 0;
            for (int e = head[c]; e != -1; e = nxt[e]) {
                int u = to[e];
                if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
            }
            if (next == 0) return c;
            c = next;
        }
    }
    static void readTree(DataInputStream in) throws IOException {
        head = new int[n + 1]; nxt = new int[2 * n]; to = new int[2 * n];
        sz = new int[n + 1]; par = new int[n + 1]; removed = new boolean[n + 1];
        gotV = new int[n + 1]; gotD = new int[n + 1];
        Arrays.fill(head, -1);
        for (int i = 0, e = 0; i < n - 1; i++) {
            int a = nextInt(in), b = nextInt(in);
            to[e] = b; nxt[e] = head[a]; head[a] = e++;
            to[e] = a; nxt[e] = head[b]; head[b] = e++;
        }
    }
    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;
    }
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        n = nextInt(in);
        int K = nextInt(in);
        readTree(in);
        long[] cnt = new long[n + 1];
        long ans = 0;
        int[] todo = new int[n + 1];
        int top = 0;
        todo[top++] = 1;
        while (top > 0) {
            int c = centroid(todo[--top]);
            removed[c] = true;
            cnt[0] = 1;
            int maxD = 0;
            for (int e = head[c]; e != -1; e = nxt[e]) {
                int u = to[e];
                if (removed[u]) continue;
                bfs(u, c, 1);
                for (int i = 0; i < gotN; i++) if (gotD[i] <= K) ans += cnt[K - gotD[i]];   // count first
                for (int i = 0; i < gotN; i++) { cnt[gotD[i]]++; maxD = Math.max(maxD, gotD[i]); }   // then add
            }
            Arrays.fill(cnt, 0, maxD + 1, 0);
            for (int e = head[c]; e != -1; e = nxt[e]) if (!removed[to[e]]) todo[top++] = to[e];
        }
        System.out.println(ans);
    }
}
7

Python

import sys

def read_tree(data, n):
    g = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
        g[a].append(b)
        g[b].append(a)
    return g

def make_tools(g, n):
    removed = [False] * (n + 1)
    par = [0] * (n + 1)
    sz = [0] * (n + 1)

    def bfs(s, frm, d0):                          # the part reachable from s, not crossing frm
        got = [(s, d0)]
        par[s] = frm
        for v, d in got:                          # the list grows while we walk it
            for u in g[v]:
                if u != par[v] and not removed[u]:
                    par[u] = v
                    got.append((u, d + 1))
        return got

    def centroid(s):
        got = bfs(s, 0, 0)
        tot = len(got)
        for v, _ in reversed(got):                # children before parents
            sz[v] = 1 + sum(sz[u] for u in g[v] if u != par[v] and not removed[u])
        c = s
        while True:
            nxt = 0
            for u in g[c]:
                if u != par[c] and not removed[u] and sz[u] * 2 > tot:
                    nxt = u
            if not nxt:
                return c
            c = nxt

    return removed, bfs, centroid

def main():
    data = sys.stdin.buffer.read().split()
    n, K = int(data[0]), int(data[1])
    g = read_tree(data, n)
    removed, bfs, centroid = make_tools(g, n)
    cnt = [0] * (n + 1)
    ans, todo = 0, [1]
    while todo:
        c = centroid(todo.pop())
        removed[c] = True
        cnt[0], top = 1, 0
        for u in g[c]:
            if removed[u]:
                continue
            got = bfs(u, c, 1)
            for _, d in got:                      # count first
                if d <= K:
                    ans += cnt[K - d]
            for _, d in got:                      # then add this branch
                cnt[d] += 1
                top = max(top, d)
        for d in range(top + 1):
            cnt[d] = 0
        todo.extend(u for u in g[c] if not removed[u])
    print(ans)

main()
7

Problem D2 · Nearest Ration Shop

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int n, sz[200001], par[200001], best[200001];
vector<int> g[200001];
bool removed[200001];
vector<pair<int, int>> got;
vector<pair<int, int>> anc[200001];       // (centroid above v, distance)
const int INF = 1e9;                       // INF + distance still fits in int

void bfs(int s, int from, int d0) {        // the part reachable from s, not crossing from
    got = {{s, d0}};
    par[s] = from;
    for (int i = 0; i < (int)got.size(); i++) {
        auto [v, d] = got[i];
        for (int u : g[v])
            if (u != par[v] && !removed[u]) {
                par[u] = v;
                got.push_back({u, d + 1});
            }
    }
}

int centroid(int s) {
    bfs(s, 0, 0);
    int tot = got.size();
    for (int i = tot - 1; i >= 0; i--) {     // sizes: children before parents
        int v = got[i].first;
        sz[v] = 1;
        for (int u : g[v]) if (u != par[v] && !removed[u]) sz[v] += sz[u];
    }
    int c = s;
    while (true) {                            // walk into any side bigger than half
        int next = 0;
        for (int u : g[c])
            if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
        if (!next) return c;
        c = next;
    }
}

void build() {
    vector<int> todo = {1};
    while (!todo.empty()) {
        int c = centroid(todo.back());
        todo.pop_back();
        bfs(c, 0, 0);                        // c's whole piece
        for (auto [v, d] : got) anc[v].push_back({c, d});
        best[c] = INF;
        removed[c] = true;
        for (int u : g[c]) if (!removed[u]) todo.push_back(u);
    }
}

void openShop(int v) {
    for (auto [c, d] : anc[v]) best[c] = min(best[c], d);
}
int nearest(int v) {
    int res = INF;
    for (auto [c, d] : anc[v]) res = min(res, best[c] + d);   // via centroid c
    return res >= INF ? -1 : res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int q;
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    build();
    while (q--) {
        int type, v;
        cin >> type >> v;
        if (type == 1) openShop(v);
        else cout << nearest(v) << "\n";
    }
}

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static int[] head, nxt, to, sz, par;
    static boolean[] removed;
    static int[] gotV, gotD;                      // the last BFS: villages and distances
    static int gotN;

    static void bfs(int s, int from, int d0) {
        gotN = 0;
        gotV[gotN] = s; gotD[gotN++] = d0;
        par[s] = from;
        for (int i = 0; i < gotN; i++) {
            int v = gotV[i];
            for (int e = head[v]; e != -1; e = nxt[e]) {
                int u = to[e];
                if (u != par[v] && !removed[u]) { par[u] = v; gotV[gotN] = u; gotD[gotN++] = gotD[i] + 1; }
            }
        }
    }
    static int centroid(int s) {
        bfs(s, 0, 0);
        int tot = gotN;
        for (int i = tot - 1; i >= 0; i--) {
            int v = gotV[i];
            sz[v] = 1;
            for (int e = head[v]; e != -1; e = nxt[e]) { int u = to[e]; if (u != par[v] && !removed[u]) sz[v] += sz[u]; }
        }
        int c = s;
        while (true) {
            int next = 0;
            for (int e = head[c]; e != -1; e = nxt[e]) {
                int u = to[e];
                if (u != par[c] && !removed[u] && sz[u] * 2 > tot) next = u;
            }
            if (next == 0) return c;
            c = next;
        }
    }
    static void readTree(DataInputStream in) throws IOException {
        head = new int[n + 1]; nxt = new int[2 * n]; to = new int[2 * n];
        sz = new int[n + 1]; par = new int[n + 1]; removed = new boolean[n + 1];
        gotV = new int[n + 1]; gotD = new int[n + 1];
        Arrays.fill(head, -1);
        for (int i = 0, e = 0; i < n - 1; i++) {
            int a = nextInt(in), b = nextInt(in);
            to[e] = b; nxt[e] = head[a]; head[a] = e++;
            to[e] = a; nxt[e] = head[b]; head[b] = e++;
        }
    }
    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;
    }
    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);
        readTree(in);
        final int INF = 1_000_000_000;
        int[] best = new int[n + 1];
        List<int[]>[] anc = new ArrayList[n + 1];   // (centroid above v, distance)
        for (int v = 1; v <= n; v++) anc[v] = new ArrayList<>();
        int[] todo = new int[n + 1];
        int top = 0;
        todo[top++] = 1;
        while (top > 0) {
            int c = centroid(todo[--top]);
            bfs(c, 0, 0);
            for (int i = 0; i < gotN; i++) anc[gotV[i]].add(new int[]{c, gotD[i]});
            best[c] = INF;
            removed[c] = true;
            for (int e = head[c]; e != -1; e = nxt[e]) if (!removed[to[e]]) todo[top++] = to[e];
        }
        StringBuilder sb = new StringBuilder();
        while (q-- > 0) {
            int type = nextInt(in), v = nextInt(in);
            if (type == 1) for (int[] p : anc[v]) best[p[0]] = Math.min(best[p[0]], p[1]);
            else {
                int res = INF;
                for (int[] p : anc[v]) res = Math.min(res, best[p[0]] + p[1]);
                sb.append(res >= INF ? -1 : res).append('\n');
            }
        }
        System.out.print(sb);
    }
}
-1
4
1
2
0

Python (float("inf") + d is still infinity, so Python has no overflow here)

import sys

def read_tree(data, n):
    g = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])
        g[a].append(b)
        g[b].append(a)
    return g

def make_tools(g, n):
    removed = [False] * (n + 1)
    par = [0] * (n + 1)
    sz = [0] * (n + 1)

    def bfs(s, frm, d0):                          # the part reachable from s, not crossing frm
        got = [(s, d0)]
        par[s] = frm
        for v, d in got:                          # the list grows while we walk it
            for u in g[v]:
                if u != par[v] and not removed[u]:
                    par[u] = v
                    got.append((u, d + 1))
        return got

    def centroid(s):
        got = bfs(s, 0, 0)
        tot = len(got)
        for v, _ in reversed(got):                # children before parents
            sz[v] = 1 + sum(sz[u] for u in g[v] if u != par[v] and not removed[u])
        c = s
        while True:
            nxt = 0
            for u in g[c]:
                if u != par[c] and not removed[u] and sz[u] * 2 > tot:
                    nxt = u
            if not nxt:
                return c
            c = nxt

    return removed, bfs, centroid

def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    g = read_tree(data, n)
    removed, bfs, centroid = make_tools(g, n)
    INF = float("inf")
    best = [INF] * (n + 1)
    anc = [[] for _ in range(n + 1)]              # (centroid above v, distance)
    todo = [1]
    while todo:
        c = centroid(todo.pop())
        for v, d in bfs(c, 0, 0):
            anc[v].append((c, d))
        removed[c] = True
        todo.extend(u for u in g[c] if not removed[u])
    out, pos = [], 2 * n
    for _ in range(q):
        t, v = data[pos], int(data[pos + 1])
        pos += 2
        if t == b"1":
            for c, d in anc[v]:
                best[c] = min(best[c], d)
        else:
            res = min(best[c] + d for c, d in anc[v])   # inf + d stays inf: no overflow in Python
            out.append(-1 if res == INF else res)
    print("\n".join(map(str, out)))

main()
-1
4
1
2
0

For n = 2 · 10^5 the Python versions can be slow under CPython; submit with PyPy if the judge offers it.