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:
- BFS the branch (distances start at 1);
- count: for every village at distance d ≤ K, add
cnt[K − d]; - 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
- 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).
- How do you find it? Compute subtree sizes from any root, then repeatedly step into a child with size > n / 2.
- 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.
- 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.
- 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.
- 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).
- 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
13instead of7. - 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.