SyntaxPilot
Courses/Competitive Programming/Lesson 52
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 52 of 90

Trees: diameter, centre, subtree sizes

queued

These are the notes for Competitive Programming episode 52, the first trees episode of the graphs section. A tree is a connected graph with no cycle, so between any two villages there is exactly one route. Three classic questions each get a slow obvious answer and a fast one you invent. Longest Trail asks for the longest route between two villages: walking from every village is correct but Time Limit Exceeded on a path of 2 · 10^5 villages, and walking only from village 1 prints 11 where 12 is right. Lifting a rope net by any knot, then by its lowest knot, gives the double sweep: two walks, O(n). The walks keep their own stack, because recursion 2 · 10^5 calls deep crashes. Wedding Venue asks for the village whose farthest guest travels least: "the busiest village" prints 2 8 where 4 6 is right, and the fact that every village's farthest village is an end of the longest trail gives every eccentricity as max(da[v], db[v]) after three walks. Total Travel asks for the sum of all pairwise distances: all pairs is TLE again, and counting how many trips use each road, size · (n − size), needs only subtree sizes. Multiplying the sizes in int prints 1589985719552 where 1333333333300000000 is right; 1LL * fixes it. Three stress tests pass. 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

Make a net of knotted ropes: every knot is a village, every rope is a road, and each rope is as long as its road. Because the net is a tree, there is only one way along the ropes from one knot to another. Lift the whole net by any knot and let it hang. The knot that hangs lowest is the farthest one from your hand, and it is always one end of the longest rope path in the net. Now lift the net by that lowest knot. The knot that hangs lowest this time is the other end, and how far it hangs is the length of the longest path. Two lifts, and you have measured the net.

For the wedding venue, a family wants to hold the wedding in the village that makes the longest guest trip as short as possible. The village with the most roads looks central, but it isn't always. The rope net helps again: whatever village you stand in, your farthest guest lives at one of the two ends of the longest path.

For total travel, the transport office wants the total length of all trips if every pair of villages travels once. Instead of measuring trip after trip, stand on each road with a counter: count the trips that cross it, multiply by its length, and add up the roads.

Problem T1 · Longest Trail

(Written for this course, in the style of an AtCoder Beginner Contest problem.)

A region has n villages joined by n − 1 two-way roads; road i joins a_i and b_i and has length w_i. Every village can reach every other one, so the roads form a tree. The tourism office wants to advertise the longest trail: the largest road distance between two villages. Print it.

  • Input: n (1 ≤ n ≤ 2 · 10^5), then n − 1 lines a_i b_i w_i (1 ≤ w_i ≤ 10^9).
  • Output: the largest distance between two villages (0 if n = 1).
Input Output
6 / 1 2 3 / 2 3 4 / 2 4 2 / 4 5 6 / 1 6 1 12 (5 – 4 – 2 – 3: 6 + 2 + 4)
1 0
2 / 1 2 7 7

The sample tree, with village 2 in the middle:

6 --1-- 1 --3-- 2 --4-- 3
                |
                2
                |
                4 --6-- 5

The longest route between two villages of a tree is called its diameter. The answer can be close to 2 · 10^5 · 10^9 = 2 · 10^14, so distances are long long.

The obvious attempt: walk from every village (TLE)

distFrom(s) walks the tree from s and records every village's distance. It keeps its own stack (a vector<int>) instead of calling itself, and it never visits a village twice (d[u] < 0 means "not reached yet"). In a tree every village is reached through its one and only route, so the order of the walk does not matter: each distance is right the first time it is written. The brute force calls it from every village and keeps the largest distance.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    cin >> n;
    g.assign(n + 1, {});
    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 best = 0;
    for (int s = 1; s <= n; s++) {           // distances from every village
        vector<ll> d = distFrom(s);
        best = max(best, *max_element(d.begin() + 1, d.end()));
    }
    cout << best << "\n";
}
12

Correct. Now one long path of 2 · 10^5 villages, built inside the program, each road 10^9 long:

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    n = 200000;                             // one long path, built here
    g.assign(n + 1, {});
    for (int v = 1; v < n; v++) {
        g[v].push_back({v + 1, 1000000000});
        g[v + 1].push_back({v, 1000000000});
    }
    ll best = 0;
    for (int s = 1; s <= n; s++) {           // distances from every village
        vector<ll> d = distFrom(s);
        best = max(best, *max_element(d.begin() + 1, d.end()));
    }
    cout << best << "\n";
}

Verdict: Time Limit Exceeded (over the 8 second limit). There are 2 · 10^5 walks of 2 · 10^5 villages each: 4 · 10^10 steps.

The shortcut: walk only from village 1 (WA)

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<ll> d1 = distFrom(1);             // just from village 1
    cout << *max_element(d1.begin() + 1, d1.end()) << "\n";
}
11

Expected 12. The 11 is the longest trail that starts at village 1 (1 – 2 – 4 – 5), but village 1 is not an end of the longest trail anywhere. One walk measures from the wrong place.

The double sweep: lift the net twice

  1. Walk from village 1 (any village works). Let a be the farthest village.
  2. Walk from a. The farthest distance from a is the diameter, and the farthest village b is the other end.
Village 1 2 3 4 5 6
d1 (from 1) 0 3 7 5 11 1
da (from a = 5) 11 8 12 6 0 12

From 1 the farthest village is 5 (11), exactly what the shortcut printed. From 5 the farthest distance is 12, reached at both 3 and 6: the trails 5 … 3 and 5 … 6 are both longest. max_element returns the first maximum, so b = 3. max_element(d1.begin() + 1, d1.end()) - d1.begin() turns the iterator into a village number; starting at begin() + 1 skips the unused slot 0.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<ll> d1 = distFrom(1);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();   // farthest from 1
    vector<ll> da = distFrom(a);
    cout << *max_element(da.begin() + 1, da.end()) << "\n";   // farthest from a
}

On the three samples (the trail, a single village, two villages):

12
0
7

On the path of 2 · 10^5 villages that broke the brute force (the same program with the reading lines replaced by the path builder from the brute-force test above):

199999000000000

That is 199 999 roads of 10^9: about 2 · 10^14, which needs long long. It runs in a few milliseconds.

Why the farthest village from anywhere is a diameter end

Let x … y be a longest trail, of length D, and start the first walk at any village s. Picture the net hanging from s: a village's depth is its distance from s.

  • The trail x … y has a highest knot c (the village of the trail closest to s). From c the trail goes down to x on one side and down to y on the other (one side may be empty if c is x or y). So D = (depth(x) − depth(c)) + (depth(y) − depth(c)).
  • a is the lowest knot of the whole net, so depth(a) ≥ depth(x) and depth(a) ≥ depth(y).
  • Climb from a up towards s. The two branches of the trail below c are separate ropes (a tree has no loops), so your climb can join at most one of them below c. For the other end, say y, the route from a to y has to come up at least as high as c before going down to y.
  • So dist(a, y) ≥ (depth(a) − depth(c)) + (depth(y) − depth(c)) ≥ (depth(x) − depth(c)) + (depth(y) − depth(c)) = D.

A trail from a can't be longer than D, so a … y is also a longest trail and a is one of its ends. The second walk, from a, then finds the far end and the exact length. The argument uses "going down never makes a route shorter", so it needs road lengths ≥ 0: with negative lengths the double sweep can fail.

Iterative DFS vs recursion depth

The usual textbook DFS calls itself for every child. On a path of 2 · 10^5 villages that is 2 · 10^5 nested calls, and each call keeps its own frame on the call stack:

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)
vector<ll> d;

void dfs(int v, int p) {                 // recursive: one call per village on the path
    for (auto [u, w] : g[v])
        if (u != p) { d[u] = d[v] + w; dfs(u, v); }
}

int main() {
    n = 200000;                             // one long path, built here
    g.assign(n + 1, {});
    for (int v = 1; v < n; v++) {
        g[v].push_back({v + 1, 1000000000});
        g[v + 1].push_back({v, 1000000000});
    }
    d.assign(n + 1, 0);
    dfs(1, 0);
    int a = max_element(d.begin() + 1, d.end()) - d.begin();
    d.assign(n + 1, 0);
    dfs(a, 0);
    cout << *max_element(d.begin() + 1, d.end()) << "\n";
}
Segmentation fault

The program crashed with exit code 139 even with Linux's default 8 MB stack. A judge reports this as Runtime Error. Python is stricter: its default recursion limit is 1000 calls.

n = 200000                                  # one long path, built here
g = [[] for _ in range(n + 1)]
for v in range(1, n):
    g[v].append((v + 1, 1000000000))
    g[v + 1].append((v, 1000000000))
d = [0] * (n + 1)

def dfs(v, p):                              # recursive
    for u, w in g[v]:
        if u != p:
            d[u] = d[v] + w
            dfs(u, v)

dfs(1, 0)
print(max(d))
RecursionError: maximum recursion depth exceeded

Raising the limit with sys.setrecursionlimit only moves the crash into the C stack. The safe fix is the one distFrom already uses: an explicit stack. Push the start; repeatedly pop a village and push every neighbour not yet reached. The stack lives on the heap, so its size is limited only by memory, and the walk visits each village once and each road twice: O(n).

The same stack walk gives a useful order for Problem T3: every village is pushed by its parent, so it is popped (and recorded) after its parent. Reading the recorded order forwards visits parents before children; reading it backwards visits children before parents.

Stress test against walks from every village

mt19937 rng(52) builds 500 random trees with up to 9 villages: village v joins a random earlier village, which always makes a tree.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    mt19937 rng(52);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 9 + 1;
        g.assign(n + 1, {});
        for (int v = 2; v <= n; v++) {          // random tree
            int p = rng() % (v - 1) + 1, w = rng() % 10 + 1;
            g[v].push_back({p, w});
            g[p].push_back({v, w});
        }
        ll slow = 0;
        for (int s = 1; s <= n; s++) {
            vector<ll> d = distFrom(s);
            slow = max(slow, *max_element(d.begin() + 1, d.end()));
        }
        vector<ll> d1 = distFrom(1);
        int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
        vector<ll> da = distFrom(a);
        ll fast = *max_element(da.begin() + 1, da.end());
        if (slow != fast) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem T2 · Wedding Venue

(Written for this course, in the style of a Codeforces Div. 2 C problem.)

Same villages and roads. A family wedding has guests from every village, and each guest travels by road to the venue. Choose the venue so that the longest guest trip is as short as possible. Print the venue and that longest trip; on a tie, print the smallest village number.

  • Input: as in Longest Trail (1 ≤ n ≤ 2 · 10^5, 1 ≤ w_i ≤ 10^9).
  • Output: the venue and its longest guest trip.
Input Output
6 / 1 2 3 / 2 3 4 / 2 4 2 / 4 5 6 / 1 6 1 4 6
4 / 1 2 5 / 1 3 5 / 1 4 5 1 5 (a star: the middle)
1 1 0

The distance from v to its farthest village is the eccentricity of v, ecc(v). The answer is a village with the smallest eccentricity: the centre of the tree.

The obvious attempt: the busiest village (WA)

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    int best = 1;
    for (int v = 1; v <= n; v++)             // the busiest village
        if (g[v].size() > g[best].size()) best = v;
    vector<ll> d = distFrom(best);
    cout << best << " " << *max_element(d.begin() + 1, d.end()) << "\n";
}
2 8

Expected 4 6. Village 2 has three roads, more than any other, but its guest from village 5 travels 2 + 6 = 8. Village 4 has only two roads, yet nobody travels more than 6 to it. The number of roads says nothing about the lengths behind them.

The farthest guest lives at a trail end

Fact. Let a … b be the longest trail found by the double sweep. For every village v, ecc(v) = max(dist(v, a), dist(v, b)).

Why. Hang the net from v, and let c be the highest knot of the trail a … b, as in the proof above. Suppose some village z hung strictly lower than both a and b. The climb from z towards v joins at most one of the trail's two branches below c, so for one end, say b, the route from z to b rises at least to c: dist(z, b) ≥ (depth(z) − depth(c)) + (depth(b) − depth(c)) > (depth(a) − depth(c)) + (depth(b) − depth(c)) = D. That is a trail longer than the longest one: impossible. So nothing hangs lower than both a and b, and the farthest village from v is a or b.

So three walks are enough: from 1 to find a, from a (giving da and b), and from b (giving db). Then every village's eccentricity is one max.

Village 1 2 3 4 5 6
roads 2 3 1 2 1 1
da (from a = 5) 11 8 12 6 0 12
db (from b = 3) 7 4 0 6 12 8
ecc = max(da, db) 11 8 12 6 12 12

The strict < in the loop keeps the smaller village number on a tie.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<ll> d1 = distFrom(1);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
    vector<ll> da = distFrom(a);             // one end of the longest trail
    int b = max_element(da.begin() + 1, da.end()) - da.begin();
    vector<ll> db = distFrom(b);             // the other end
    int best = 1;
    for (int v = 1; v <= n; v++)             // farthest guest of v: a or b
        if (max(da[v], db[v]) < max(da[best], db[best])) best = v;
    cout << best << " " << max(da[best], db[best]) << "\n";
}

On the three samples:

4 6
1 5
1 0

On the path of 2 · 10^5 villages (again the reading lines replaced by the path builder):

100000 100000000000000

Villages 100 000 and 100 001 are both 99 999 · 10^9 from one end and 10^5 · 10^9 from the other, so both have eccentricity 10^14; the tie goes to 100 000, the middle of the path. The centre always lies on the longest trail, near its middle, and its eccentricity is at least D / 2.

Stress test: try every village as the venue

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    mt19937 rng(52);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 9 + 1;
        g.assign(n + 1, {});
        for (int v = 2; v <= n; v++) {          // random tree
            int p = rng() % (v - 1) + 1, w = rng() % 10 + 1;
            g[v].push_back({p, w});
            g[p].push_back({v, w});
        }
        int sb = 1;                             // brute: every village
        ll se = LLONG_MAX;
        for (int v = 1; v <= n; v++) {
            vector<ll> d = distFrom(v);
            ll e = *max_element(d.begin() + 1, d.end());
            if (e < se) se = e, sb = v;
        }
        vector<ll> d1 = distFrom(1);
        int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
        vector<ll> da = distFrom(a);
        int b = max_element(da.begin() + 1, da.end()) - da.begin();
        vector<ll> db = distFrom(b);
        int best = 1;
        for (int v = 1; v <= n; v++)
            if (max(da[v], db[v]) < max(da[best], db[best])) best = v;
        if (best != sb || max(da[best], db[best]) != se) {
            cout << "mismatch on test " << t;
            return 0;
        }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem T3 · Total Travel

(Written for this course.)

Same villages and roads. Every pair of villages makes one trip along its route. Print the total length of all n(n − 1)/2 trips.

  • Input: n (1 ≤ n ≤ 2 · 10^5), then n − 1 lines a_i b_i w_i (1 ≤ w_i ≤ 1000).
  • Output: the sum of the distances over all pairs of villages (it fits in long long).
Input Output
4 / 1 2 1 / 2 3 2 / 2 4 3 18
6 / 1 2 3 / 2 3 4 / 2 4 2 / 4 5 6 / 1 6 1 95
1 0

In the first sample the six trips are 1–2: 1, 1–3: 3, 1–4: 4, 2–3: 2, 2–4: 3, 3–4: 5, which add up to 18. For n = 2 · 10^5 there are about 2 · 10^10 trips.

The obvious attempt: every pair (TLE)

Walk from every village and add every distance. Each pair is counted twice (once from each end), so halve the total.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    cin >> n;
    g.assign(n + 1, {});
    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 total = 0;
    for (int s = 1; s <= n; s++) {           // every pair, twice
        vector<ll> d = distFrom(s);
        for (int v = 1; v <= n; v++) total += d[v];
    }
    cout << total / 2 << "\n";
}
18

Correct. On the long path, built the same way but with roads of length 1000 (g[v].push_back({v + 1, 1000});):

Verdict: Time Limit Exceeded (over the 8 second limit): again n walks of n villages, 4 · 10^10 steps.

Count per road, not per pair

Turn the question around. The total length of all trips is the sum over roads of (road length) × (number of trips that use the road). So for each road we need only one count.

Hang the tree from village 1. Each road joins a village v to its parent. The subtree of v is v together with everything hanging below it; its number of villages is the subtree size sz[v].

Why a road is used by sz · (n − sz) trips. Removing the road v–parent splits the tree into two parts: the sz[v] villages of v's subtree and the n − sz[v] villages outside it. A trip between two villages on different sides must use this road, since it is the only connection between the sides. A trip between two villages on the same side never uses it: its route stays on that side, because crossing the road and coming back would use the same road twice, which a route in a tree never does. So exactly sz[v] · (n − sz[v]) trips cross the road, one for each choice of an inside village and an outside village.

Road (rooted at 1) sz below inside × outside × length adds
1–2 3 3 × 1 = 3 × 1 3
2–3 1 1 × 3 = 3 × 2 6
2–4 1 1 × 3 = 3 × 3 9
total 18

For the six-village sample: road 1–6 adds 1 · 5 · 1 = 5, road 1–2 adds 4 · 2 · 3 = 24, road 2–3 adds 1 · 5 · 4 = 20, road 2–4 adds 2 · 4 · 2 = 16 (the slide's 8 trips × 2 km), and road 4–5 adds 1 · 5 · 6 = 30: 95 in total.

Subtree sizes in one walk. The stack walk records order with parents before children, plus each village's parent par and the length up of the road to its parent. Then go through order backwards (children before parents): when v is reached, sz[v] is final, so add it into sz[par[v]] and add the road's contribution. Index 0 of order is the root, which has no road above it, so the loop stops at i = 1.

The int overflow

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<int> par(n + 1, 0), up(n + 1, 0), order, sz(n + 1, 1);
    vector<int> st = {1};
    par[1] = -1;
    while (!st.empty()) {                    // parents before children
        int v = st.back();
        st.pop_back();
        order.push_back(v);
        for (auto [u, w] : g[v])
            if (u != par[v]) { par[u] = v; up[u] = w; st.push_back(u); }
    }
    ll total = 0;
    for (int i = n - 1; i > 0; i--) {        // children before parents
        int v = order[i];
        sz[par[v]] += sz[v];
        total += sz[v] * (n - sz[v]) * up[v];   // pairs using road v–par
    }
    cout << total << "\n";
}
18

Right on the sample. On the long path:

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

int main() {
    n = 200000;                             // one long path, built here
    g.assign(n + 1, {});
    for (int v = 1; v < n; v++) {
        g[v].push_back({v + 1, 1000});
        g[v + 1].push_back({v, 1000});
    }
    vector<int> par(n + 1, 0), up(n + 1, 0), order, sz(n + 1, 1);
    vector<int> st = {1};
    par[1] = -1;
    while (!st.empty()) {                    // parents before children
        int v = st.back();
        st.pop_back();
        order.push_back(v);
        for (auto [u, w] : g[v])
            if (u != par[v]) { par[u] = v; up[u] = w; st.push_back(u); }
    }
    ll total = 0;
    for (int i = n - 1; i > 0; i--) {        // children before parents
        int v = order[i];
        sz[par[v]] += sz[v];
        total += sz[v] * (n - sz[v]) * up[v];   // pairs using road v–par
    }
    cout << total << "\n";
}
1589985719552

The real answer is 1333333333300000000. In the middle of the path sz = 10^5 and n − sz = 10^5, so sz[v] * (n - sz[v]) is 10^10, far above the int limit 2^31 − 1 ≈ 2.1 · 10^9. All three factors are int, so the product is computed in int and overflows before total (a long long) ever sees it. Signed overflow is undefined behaviour in C++; here it produced a wrong number with no warning.

The fix: 1LL first

1LL is the number 1 as a long long. Written first, it makes 1LL * sz[v] a long long, and every later multiplication is done in long long too.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<int> par(n + 1, 0), up(n + 1, 0), order, sz(n + 1, 1);
    vector<int> st = {1};
    par[1] = -1;
    while (!st.empty()) {                    // parents before children
        int v = st.back();
        st.pop_back();
        order.push_back(v);
        for (auto [u, w] : g[v])
            if (u != par[v]) { par[u] = v; up[u] = w; st.push_back(u); }
    }
    ll total = 0;
    for (int i = n - 1; i > 0; i--) {        // children before parents
        int v = order[i];
        sz[par[v]] += sz[v];
        total += 1LL * sz[v] * (n - sz[v]) * up[v];   // pairs using road v–par
    }
    cout << total << "\n";
}

On the three samples:

18
95
0

On the long path (the path builder of the overflow test above in place of the reading lines):

1333333333300000000

For a path of n villages and roads of length 1000, road i has i villages on one side and n − i on the other, and the total is 1000 · (n³ − n) / 6 = 1 333 333 333 300 000 000, exactly what was printed, in milliseconds. Placing 1LL at the end does not help: with total += sz[v] * (n - sz[v]) * 1LL * up[v]; the first product has already overflowed, and the same program printed 59789630690080000.

Stress test against every pair

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    mt19937 rng(52);
    for (int t = 1; t <= 500; t++) {
        n = rng() % 9 + 1;
        g.assign(n + 1, {});
        for (int v = 2; v <= n; v++) {          // random tree
            int p = rng() % (v - 1) + 1, w = rng() % 10 + 1;
            g[v].push_back({p, w});
            g[p].push_back({v, w});
        }
        ll slow = 0;
        for (int s = 1; s <= n; s++) {
            vector<ll> d = distFrom(s);
            for (int v = 1; v <= n; v++) slow += d[v];
        }
        slow /= 2;
        vector<int> par(n + 1, 0), up(n + 1, 0), order, sz(n + 1, 1);
        vector<int> st = {1};
        par[1] = -1;
        while (!st.empty()) {                    // parents before children
            int v = st.back();
            st.pop_back();
            order.push_back(v);
            for (auto [u, w] : g[v])
                if (u != par[v]) { par[u] = v; up[u] = w; st.push_back(u); }
        }
        ll total = 0;
        for (int i = n - 1; i > 0; i--) {        // children before parents
            int v = order[i];
            sz[par[v]] += sz[v];
            total += 1LL * sz[v] * (n - sz[v]) * up[v];
        }
        if (slow != total) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Memory Verdict
walk from every village (diameter, centre, all pairs) O(n²) O(n) TLE at n = 2 · 10^5 (4 · 10^10 steps)
one walk from village 1 O(n) O(n) Wrong Answer (11)
double sweep O(n): 2 walks O(n) accepted, milliseconds
recursive DFS on a path O(n) O(n) call stack Runtime Error (stack overflow)
busiest village O(n) O(n) Wrong Answer (2 8)
centre with max(da, db) O(n): 3 walks O(n) accepted
subtree sizes, size · (n − size) · w O(n): 1 walk + 1 backward pass O(n) accepted (with 1LL)
rerooting (homework 3) O(n) O(n) accepted
pairs at distance ≤ k by n walks (homework 4) O(n²) O(n) fine for n ≤ 5000

Common mistakes (and the real outputs)

Mistake What you see Why Fix
walk from every village Time Limit Exceeded n walks of n villages double sweep, centre trick, subtree sizes
farthest from village 1 only 11 (expected 12) village 1 is not a trail end walk again from the farthest village
the busiest village as the centre 2 8 (expected 4 6) many roads ≠ short trips ecc(v) = max(da[v], db[v])
sz[v] * (n - sz[v]) * up[v] in int 1589985719552 (expected 1333333333300000000) 10^10 > 2^31 − 1 1LL * sz[v] * ...
1LL at the end of the product 59789630690080000 the first product already overflowed put 1LL first
recursive DFS on a 2 · 10^5 path Segmentation fault (Runtime Error) 2 · 10^5 nested calls your own stack
recursive DFS in Python RecursionError: maximum recursion depth exceeded limit of 1000 calls your own stack
distances in int wrapped distances up to 2 · 10^14 long long distances
including slot 0 in max_element village 0 chosen as an end villages are numbered from 1 start at begin() + 1
double sweep with negative road lengths Wrong Answer the lifting argument needs lengths ≥ 0 DP on the tree (homework 2)

Mini project

Write a tree toolbox with distFrom(s), diameter() (returning the length and both ends), eccentricities(), centre(), subtreeSizes(root) and sumOfAllDistances(), all iterative. Build four kinds of test trees: a path, a star, a "caterpillar" (a path with a leaf on every village) and a random tree, for n = 10, 1000 and 2 · 10^5. For the small ones print the tree as an edge list and check every function against the walk-from-every-village brute force. For the big ones time each function and confirm they all stay linear (doubling n should roughly double the time). As a bonus, print the villages of the longest trail and mark the centre on it.

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. Print the diameter's villages. Same input as Longest Trail. Print the length of the longest trail, the number of villages on it, and the villages in order from one end to the other.

Solution

Record each village's parent during the second walk (the village it was reached from). After the walk from a, the parents all point back towards a, so following them from b to a lists the trail. Reverse it to go from a to b.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s, vector<int> &par) {   // also records each village's parent
    vector<ll> d(n + 1, -1);
    par.assign(n + 1, 0);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; par[u] = v; st.push_back(u); }
    }
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<int> par;
    vector<ll> d1 = distFrom(1, par);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
    vector<ll> da = distFrom(a, par);                 // par now points towards a
    int b = max_element(da.begin() + 1, da.end()) - da.begin();
    vector<int> path;
    for (int v = b; v != a; v = par[v]) path.push_back(v);   // walk back from b to a
    path.push_back(a);
    reverse(path.begin(), path.end());                // a ... b
    cout << da[b] << "\n" << path.size() << "\n";
    for (int v : path) cout << v << " ";
    cout << "\n";
}

The three Longest Trail samples:

12
4
5 4 2 3
0
1
1
7
2
2 1

2. Diameter by DP: the two deepest children. Same input and output as Longest Trail, but compute it with dynamic programming on the rooted tree instead of the double sweep.

Solution

Root the tree at 1. Let down[v] be the longest path going down from v. Every trail has a highest village v (its top), and the longest trail with top v goes down into v's two deepest children: d1 + d2, where each child u offers down[u] + w(v, u). So process villages children before parents, keep the two largest values d1 ≥ d2, set down[v] = d1 and update the answer with d1 + d2. This version also works with negative road lengths if you start d1 and d2 at 0 (a trail may be a single village).

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> g(n + 1);   // (neighbour, length)
    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});
    }
    vector<int> par(n + 1, 0), order;
    vector<int> st = {1};
    par[1] = -1;
    while (!st.empty()) {                      // parents before children
        int v = st.back();
        st.pop_back();
        order.push_back(v);
        for (auto [u, w] : g[v])
            if (u != par[v]) { par[u] = v; st.push_back(u); }
    }
    vector<ll> down(n + 1, 0);                 // deepest path going down from v
    ll best = 0;
    for (int i = n - 1; i >= 0; i--) {         // children before parents
        int v = order[i];
        ll d1 = 0, d2 = 0;                     // the two deepest children (with their road)
        for (auto [u, w] : g[v]) {
            if (u == par[v]) continue;
            ll c = down[u] + w;
            if (c > d1) { d2 = d1; d1 = c; }
            else if (c > d2) d2 = c;
        }
        down[v] = d1;
        best = max(best, d1 + d2);             // the longest trail whose top is v
    }
    cout << best << "\n";
}

The three Longest Trail samples, and the four-village tree of Total Travel (3 – 2 – 4 is 2 + 3 = 5):

12
0
7
5

3. Sum of distances from every village. Same input as Total Travel. For every village v print the sum of its distances to all other villages.

Solution

Rerooting. First compute ans[1], the sum of depths from village 1, and every subtree size. Now move the root from a parent p to its child v across a road of length w: the sz[v] villages of v's subtree get w closer, and the other n − sz[v] get w farther. So ans[v] = ans[p] + w · (n − 2 · sz[v]). Visiting villages parents before children fills every answer in O(n). As a check, the answers add up to twice the Total Travel answer.

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<vector<pair<int, int>>> g(n + 1);   // (neighbour, length)
    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});
    }
    vector<int> par(n + 1, 0), up(n + 1, 0), order, sz(n + 1, 1);
    vector<ll> depth(n + 1, 0);
    vector<int> st = {1};
    par[1] = -1;
    while (!st.empty()) {                      // parents before children
        int v = st.back();
        st.pop_back();
        order.push_back(v);
        for (auto [u, w] : g[v])
            if (u != par[v]) { par[u] = v; up[u] = w; depth[u] = depth[v] + w; st.push_back(u); }
    }
    for (int i = n - 1; i > 0; i--) sz[par[order[i]]] += sz[order[i]];   // subtree sizes
    vector<ll> ans(n + 1, 0);
    for (int v = 1; v <= n; v++) ans[1] += depth[v];   // sum of distances from the root
    for (int i = 1; i < n; i++) {              // parents before children: reroot one road at a time
        int v = order[i];
        // moving from par[v] to v: sz[v] villages get closer by up[v], n - sz[v] get farther
        ans[v] = ans[par[v]] + 1LL * up[v] * (n - 2LL * sz[v]);
    }
    for (int v = 1; v <= n; v++) cout << ans[v] << " ";
    cout << "\n";
}

On the Total Travel samples 4 / 1 2 1 / 2 3 2 / 2 4 3 (8 + 6 + 10 + 12 = 36 = 2 · 18), the six-village tree (sum 190 = 2 · 95) and a single village:

8 6 10 12
27 21 37 25 49 31
0

4. Count pairs at distance ≤ k (preview). Input: n and k, then the n − 1 roads. Count the pairs of villages whose distance is at most k. Here n ≤ 5000.

Solution

For small n, n walks are fine: walk from every village s and count the villages v > s with d[v] ≤ k (each pair once). That is O(n²): 2.5 · 10^7 steps for n = 5000. For n = 2 · 10^5 it is TLE, and the fast method, splitting the tree at its centroid again and again, is coming later in the course.

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll k;
    cin >> n >> k;
    g.assign(n + 1, {});
    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 pairs = 0;
    for (int s = 1; s <= n; s++) {          // n walks: O(n²), fine for n ≤ 5000
        vector<ll> d = distFrom(s);
        for (int v = s + 1; v <= n; v++)    // each pair once (v > s)
            if (d[v] <= k) pairs++;
    }
    cout << pairs << "\n";
}

Input 4 3 with the Total Travel roads (pairs 1–2, 1–3, 2–3, 2–4), and 6 8 with the Longest Trail roads:

4
12

Quick quiz

A tree has 10 villages. Below road r hang 3 villages. How many of the 45 trips use road r?

total += 1LL * sz[v] * (n - sz[v]) * up[v];

A) 3 · B) 7 · C) 21 · D) 45

Answer

C. A trip uses road r exactly when one end is among the 3 villages below it and the other is among the 7 above it: 3 × 7 = 21.

Interview questions

  1. How do you find the diameter of a tree in O(n)? Walk from any vertex to the farthest vertex a, then walk from a; the largest distance is the diameter (the double sweep, or "double BFS/DFS"). Alternatively, a DP with the two deepest children of every vertex.
  2. Why does the double sweep work? The farthest vertex from any vertex is an end of some diameter (the hanging argument above). It needs non-negative edge weights.
  3. What is the centre of a tree and how do you find it? The vertex with the smallest eccentricity. After the double sweep with ends a and b, ecc(v) = max(dist(v, a), dist(v, b)), so three walks give every eccentricity. In an unweighted tree there are one or two centres, the middle vertex or vertices of a diameter.
  4. How do you compute the sum of distances over all pairs? Each edge (v, parent) is used by sz[v] · (n − sz[v]) pairs; sum that times the weight. O(n) with subtree sizes.
  5. How do you get the sum of distances from every vertex? Rerooting: ans[child] = ans[parent] + w · (n − 2 · sz[child]).
  6. Why avoid recursive DFS in contests? A path of 2 · 10^5 vertices means 2 · 10^5 nested calls, which can overflow the call stack (Runtime Error), and Python stops at 1000 calls. Use an explicit stack and a recorded order.
  7. What overflows in the sum-of-distances formula? sz · (n − sz) reaches 10^10 in int. Cast before multiplying: 1LL * sz * (n - sz) * w.

Glossary

Term Meaning Example
Graph Villages (vertices) joined by roads (edges) the region map
Tree A connected graph with no cycle; n vertices, n − 1 edges the six-village sample
Route (path) A sequence of roads from one village to another without repeating a village; unique in a tree 5 – 4 – 2 – 3
Distance The total length of the route between two villages dist(5, 3) = 12
Cycle (loop) A route that returns to its start; a tree has none (none in a tree)
Path graph A tree that is one long line the 2 · 10^5-village test
Star A tree where one village is joined to all others 4 / 1 2 5 / 1 3 5 / 1 4 5
Adjacency list For each village, the list of (neighbour, length) pairs g[v]
Degree The number of roads at a village village 2 has 3
Rooted tree A tree with one village chosen as the top (the root) hang from village 1
Root The top village of a rooted tree village 1
Parent / child In a rooted tree, the neighbour towards the root / a neighbour away from it 2 is the parent of 4
Leaf A village with no children (degree 1 in an unrooted tree) 3, 5, 6
Depth The distance from the root (or from the village the net hangs from) depth(5) = 11 from village 1
Subtree A village together with everything below it the subtree of 4 is {4, 5}
Subtree size The number of villages in a subtree sz[4] = 2
Diameter The longest distance between two villages of a tree, or the route itself 12 (5 … 3)
Eccentricity The distance from a village to its farthest village ecc(4) = 6
Centre A village with the smallest eccentricity village 4
Double sweep Walk from any village to the farthest a, then walk from a: finds the diameter Longest Trail
Walk (traversal) Visiting every village reachable from a start distFrom(s)
DFS (depth-first search) A walk that goes as deep as it can before backing up the recursive dfs
Iterative DFS A DFS-style walk that uses its own stack instead of recursion distFrom, the order walk
Explicit stack A vector used as a stack: push with push_back, pop with back + pop_back vector<int> st = {s};
Recursion A function that calls itself dfs(u, v)
Call stack The memory where each active function call keeps its frame 8 MB by default on Linux
Recursion depth How many calls are active at once 2 · 10^5 on a path
Stack overflow / segmentation fault The crash when the call stack runs out exit code 139
RecursionError Python's error when the recursion limit (1000) is passed the recursive Python walk
Order (parents before children) The order villages leave the stack: a village after its parent; backwards, children first order in Total Travel
max_element Returns an iterator to the first largest element of a range max_element(d.begin() + 1, d.end())
Overflow A result too large for its type, which wraps or breaks 1589985719552
int 32-bit signed integer, at most 2^31 − 1 ≈ 2.1 · 10^9 sz[v]
long long 64-bit signed integer, at most about 9.2 · 10^18 1333333333300000000
1LL The value 1 as a long long, used to force 64-bit multiplication 1LL * sz[v] * (n - sz[v])
Dynamic programming (DP) Building answers for big parts from answers for smaller parts homework 2
Rerooting Moving the root across one road and updating an answer in O(1) homework 3
Centroid A village whose removal leaves parts of size at most n/2; used for path counting homework 4 preview
LCA (lowest common ancestor) The deepest village that is an ancestor of two given villages next episode
Brute force Trying every possibility walk from every village
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
mt19937 C++'s Mersenne Twister random number generator mt19937 rng(52);
O(n), O(n²) Running time growing linearly / quadratically with n 2 walks / n walks
Time Limit Exceeded (TLE) The program is too slow for the time limit walks from every village
Wrong Answer (WA) The program prints a wrong output 11, 2 8
Runtime Error (RE) The program crashes deep recursion

Summary

  • A tree has exactly one route between any two villages; distances from one village take one walk, O(n).
  • Walking from every village is O(n²): TLE at n = 2 · 10^5. Walking only from village 1 prints 11, not 12.
  • Double sweep: the farthest village a from anywhere is a diameter end; the farthest distance from a is the diameter. Two walks.
  • Walk with your own stack: recursion 2 · 10^5 deep crashes (segmentation fault, RecursionError in Python).
  • Centre: ecc(v) = max(da[v], db[v]) for the diameter ends a and b; three walks. The busiest village is not the centre (2 8, not 4 6).
  • Total travel: each road is used by sz · (n − sz) trips; get subtree sizes with one walk and a backward pass, children before parents.
  • Multiply with 1LL first: in int the answer 1333333333300000000 becomes 1589985719552.

Solutions in C++, Java and Python

Problem T1 · Longest Trail

C++

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<ll> d1 = distFrom(1);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();   // farthest from 1
    vector<ll> da = distFrom(a);
    cout << *max_element(da.begin() + 1, da.end()) << "\n";   // farthest from a
}

Java (adjacency lists in arrays, an array as the stack, StreamTokenizer for fast input)

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

public class Main {
    static int n;
    static int[] head, nxt, to, len;               // adjacency lists in arrays

    static long[] distFrom(int s) {                // iterative: own stack, no recursion
        long[] d = new long[n + 1];
        Arrays.fill(d, -1);
        int[] st = new int[n];
        int top = 0;
        st[top++] = s;
        d[s] = 0;
        while (top > 0) {
            int v = st[--top];
            for (int e = head[v]; e != -1; e = nxt[e])
                if (d[to[e]] < 0) { d[to[e]] = d[v] + len[e]; st[top++] = to[e]; }
        }
        return d;
    }

    static int argmax(long[] d) {
        int best = 1;
        for (int v = 2; v <= n; v++) if (d[v] > d[best]) best = v;
        return best;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); n = (int) st.nval;
        head = new int[n + 1];
        Arrays.fill(head, -1);
        nxt = new int[2 * n]; to = new int[2 * n]; len = new int[2 * n];
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            st.nextToken(); int w = (int) st.nval;
            to[cnt] = b; len[cnt] = w; nxt[cnt] = head[a]; head[a] = cnt++;
            to[cnt] = a; len[cnt] = w; nxt[cnt] = head[b]; head[b] = cnt++;
        }
        int a = argmax(distFrom(1));               // farthest from 1: a diameter end
        long[] da = distFrom(a);
        System.out.println(da[argmax(da)]);        // farthest from a
    }
}
12
0
7

Python (an explicit list as the stack, all input read at once)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    g = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b, w = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
        g[a].append((b, w))
        g[b].append((a, w))

    def dist_from(s):                           # iterative: own stack, no recursion
        d = [-1] * (n + 1)
        d[s] = 0
        st = [s]
        while st:
            v = st.pop()
            dv = d[v]
            for u, w in g[v]:
                if d[u] < 0:
                    d[u] = dv + w
                    st.append(u)
        return d

    d1 = dist_from(1)
    a = max(range(1, n + 1), key=d1.__getitem__)   # farthest from 1
    da = dist_from(a)
    print(max(da[1:]))                             # farthest from a

main()
12
0
7

Problem T2 · Wedding Venue

C++

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

vector<ll> distFrom(int s) {                // iterative: no deep recursion
    vector<ll> d(n + 1, -1);
    vector<int> st = {s};
    d[s] = 0;
    while (!st.empty()) {
        int v = st.back();
        st.pop_back();
        for (auto [u, w] : g[v])
            if (d[u] < 0) { d[u] = d[v] + w; st.push_back(u); }
    }
    return d;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<ll> d1 = distFrom(1);
    int a = max_element(d1.begin() + 1, d1.end()) - d1.begin();
    vector<ll> da = distFrom(a);             // one end of the longest trail
    int b = max_element(da.begin() + 1, da.end()) - da.begin();
    vector<ll> db = distFrom(b);             // the other end
    int best = 1;
    for (int v = 1; v <= n; v++)             // farthest guest of v: a or b
        if (max(da[v], db[v]) < max(da[best], db[best])) best = v;
    cout << best << " " << max(da[best], db[best]) << "\n";
}

Java

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

public class Main {
    static int n;
    static int[] head, nxt, to, len;               // adjacency lists in arrays

    static long[] distFrom(int s) {                // iterative: own stack, no recursion
        long[] d = new long[n + 1];
        Arrays.fill(d, -1);
        int[] st = new int[n];
        int top = 0;
        st[top++] = s;
        d[s] = 0;
        while (top > 0) {
            int v = st[--top];
            for (int e = head[v]; e != -1; e = nxt[e])
                if (d[to[e]] < 0) { d[to[e]] = d[v] + len[e]; st[top++] = to[e]; }
        }
        return d;
    }

    static int argmax(long[] d) {
        int best = 1;
        for (int v = 2; v <= n; v++) if (d[v] > d[best]) best = v;
        return best;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); n = (int) st.nval;
        head = new int[n + 1];
        Arrays.fill(head, -1);
        nxt = new int[2 * n]; to = new int[2 * n]; len = new int[2 * n];
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            st.nextToken(); int w = (int) st.nval;
            to[cnt] = b; len[cnt] = w; nxt[cnt] = head[a]; head[a] = cnt++;
            to[cnt] = a; len[cnt] = w; nxt[cnt] = head[b]; head[b] = cnt++;
        }
        int a = argmax(distFrom(1));
        long[] da = distFrom(a);                   // one end of the longest trail
        long[] db = distFrom(argmax(da));          // the other end
        int best = 1;
        for (int v = 1; v <= n; v++)               // ecc(v) = max(da[v], db[v])
            if (Math.max(da[v], db[v]) < Math.max(da[best], db[best])) best = v;
        System.out.println(best + " " + Math.max(da[best], db[best]));
    }
}
4 6
1 5
1 0

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    g = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b, w = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
        g[a].append((b, w))
        g[b].append((a, w))

    def dist_from(s):                           # iterative: own stack, no recursion
        d = [-1] * (n + 1)
        d[s] = 0
        st = [s]
        while st:
            v = st.pop()
            dv = d[v]
            for u, w in g[v]:
                if d[u] < 0:
                    d[u] = dv + w
                    st.append(u)
        return d

    d1 = dist_from(1)
    a = max(range(1, n + 1), key=d1.__getitem__)
    da = dist_from(a)                              # one end of the longest trail
    b = max(range(1, n + 1), key=da.__getitem__)
    db = dist_from(b)                              # the other end
    best = 1
    for v in range(1, n + 1):                      # ecc(v) = max(da[v], db[v])
        if max(da[v], db[v]) < max(da[best], db[best]):
            best = v
    print(best, max(da[best], db[best]))

main()
4 6
1 5
1 0

Problem T3 · Total Travel

C++

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

int n;
vector<vector<pair<int, int>>> g;        // (neighbour, length)

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    g.assign(n + 1, {});
    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});
    }
    vector<int> par(n + 1, 0), up(n + 1, 0), order, sz(n + 1, 1);
    vector<int> st = {1};
    par[1] = -1;
    while (!st.empty()) {                    // parents before children
        int v = st.back();
        st.pop_back();
        order.push_back(v);
        for (auto [u, w] : g[v])
            if (u != par[v]) { par[u] = v; up[u] = w; st.push_back(u); }
    }
    ll total = 0;
    for (int i = n - 1; i > 0; i--) {        // children before parents
        int v = order[i];
        sz[par[v]] += sz[v];
        total += 1LL * sz[v] * (n - sz[v]) * up[v];   // pairs using road v–par
    }
    cout << total << "\n";
}

Java (1L * first: the same overflow exists in Java)

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        st.nextToken(); int n = (int) st.nval;
        int[] head = new int[n + 1];
        Arrays.fill(head, -1);
        int[] nxt = new int[2 * n], to = new int[2 * n], len = new int[2 * n];
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            st.nextToken(); int a = (int) st.nval;
            st.nextToken(); int b = (int) st.nval;
            st.nextToken(); int w = (int) st.nval;
            to[cnt] = b; len[cnt] = w; nxt[cnt] = head[a]; head[a] = cnt++;
            to[cnt] = a; len[cnt] = w; nxt[cnt] = head[b]; head[b] = cnt++;
        }
        int[] par = new int[n + 1], up = new int[n + 1], order = new int[n], sz = new int[n + 1];
        int[] stack = new int[n];
        int top = 0, k = 0;
        stack[top++] = 1;
        par[1] = -1;
        while (top > 0) {                          // parents before children
            int v = stack[--top];
            order[k++] = v;
            for (int e = head[v]; e != -1; e = nxt[e])
                if (to[e] != par[v]) { par[to[e]] = v; up[to[e]] = len[e]; stack[top++] = to[e]; }
        }
        Arrays.fill(sz, 1);
        long total = 0;
        for (int i = n - 1; i > 0; i--) {          // children before parents
            int v = order[i];
            sz[par[v]] += sz[v];
            total += 1L * sz[v] * (n - sz[v]) * up[v];   // pairs using road v–par
        }
        System.out.println(total);
    }
}
18
95
0

Python (Python integers never overflow)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    g = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b, w = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
        g[a].append((b, w))
        g[b].append((a, w))
    par = [0] * (n + 1)
    up = [0] * (n + 1)
    par[1] = -1
    order = []
    st = [1]
    while st:                                   # parents before children
        v = st.pop()
        order.append(v)
        for u, w in g[v]:
            if u != par[v]:
                par[u] = v
                up[u] = w
                st.append(u)
    sz = [1] * (n + 1)
    total = 0
    for i in range(n - 1, 0, -1):               # children before parents
        v = order[i]
        sz[par[v]] += sz[v]
        total += sz[v] * (n - sz[v]) * up[v]    # Python ints never overflow
    print(total)

main()
18
95
0

All three Java and Python solutions were also run on a path of 2 · 10^5 villages and on a random tree of 2 · 10^5 villages, with the same outputs as the C++ solutions (199999000000000, 100000 100000000000000 and 1333333333300000000 on the path); on the path each one finished in under 0.3 seconds.