SyntaxPilot
Courses/Competitive Programming/Lesson 38

Competitive Programming · Lesson 38 of 90 · 10 min

DP 7: DP on trees and rerooting

queued

These are the notes for Competitive Programming episode 38, part seven of the dynamic programming section. A district of n villages is joined by n − 1 roads, so the map is a tree. An original problem, Ration Shop, asks, for every village, the total walking distance if the shop were built there. A BFS from every village is right but O(n²): TLE at n = 2 · 10^5. Rooting the tree at village 1 gives a tree DP: subtree sizes sz and distance sums down, built from the children, which answers village 1 only. Then rerooting: moving the shop one road from p to its child c changes the total by − sz[c] + (n − sz[c]), so every answer comes in O(n). 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

The council of a district with n villages will build one ration shop. Everyone walks to it along the roads; the cost of a spot is the total number of roads walked by all villages. To compare spots fairly, the council wants that total for every village. There are n − 1 roads and every village can reach every other, so there is exactly one path between any two villages: the road map is a tree.

Problem O · Ration Shop

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

Given a tree with n vertices, print for every vertex v the value Σ over all u of dist(u, v), where dist counts edges.

  • Input: n (1 ≤ n ≤ 2 · 10^5), then n − 1 lines a b (an edge).
  • Output: n numbers, the answer for vertices 1 … n.

Sample 1:

6
1 2
1 3
3 4
3 5
5 6

Output: 9 13 7 11 9 13. Village 3 is the best spot (total 7). Sample 2: 1 → 0.

Attempt 1: a BFS from every village (Time Limit Exceeded)

BFS (breadth-first search) visits vertices in order of distance from a start, so it gives every distance from s in O(n).

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

int main() {
    int n;
    cin >> n;
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int s = 1; s <= n; s++) {          // shop at s: BFS from s
        vector<int> dist(n + 1, -1);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        ll total = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            total += dist[v];
            for (int u : adj[v]) if (dist[u] == -1) { dist[u] = dist[v] + 1; q.push(u); }
        }
        cout << total << " \n"[s == n];
    }
    return 0;
}

Sample 1 prints 9 13 7 11 9 13 (correct). With n = 2 · 10^5 (a random tree built inside main) it gets Time Limit Exceeded: n searches of n steps each, 4 · 10^10.

Step 1: root the tree, think in subtrees

Pick village 1 as the root and let the tree hang from it. Every other village gets a parent (the next village towards the root); its children are the neighbours below it. The subtree of v is v plus everything hanging below it. A subtree's answer can be built from its children's answers: that is DP on a tree.

  • sz[v] = number of villages in v's subtree = 1 + Σ sz[c] over children c.
  • down[v] = total walking from v's subtree to v = Σ (down[c] + sz[c]): everyone in c's subtree walks to c (down[c]) and then one more road up to v (sz[c] roads in total).

For sample 1 (rooted at 1):

village 1 2 3 4 5 6
children 2, 3 – 4, 5 – 6 –
sz 6 1 4 1 2 1
down 9 0 4 0 1 0

down[1] = (0 + 1) + (4 + 4) = 9, the answer for village 1.

Order without recursion. A BFS from the root lists the vertices so that every parent comes before its children. Walking that list backwards processes children before parents (pass 1).

#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<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<ll> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    cout << "village 1: " << down[1] << "\n";
    return 0;
}

Sample 1 prints village 1: 9.

Step 2: rerooting

Move the shop one road, from village p to its child c:

  • the sz[c] villages in c's subtree each walk one road less;
  • the other n − sz[c] villages each walk one road more.

ans[c] = ans[p] − sz[c] + (n − sz[c])

From village 1 (9) to village 3: 9 − 4 + (6 − 4) = 7. Walking the BFS list forwards (parents before children) fills every answer (pass 2). This is rerooting: compute one root with a tree DP, then move the root one edge at a time with an O(1) fix.

The accepted solution

#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<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<ll> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {           // pass 2: parents before children
        int v = order[i], p = par[v];
        ans[v] = ans[p] - sz[v] + (n - sz[v]);   // move the shop from p to v
    }
    for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
    return 0;
}
Input Output
sample 1 9 13 7 11 9 13
1 (one village) 0

The 2 · 10^5-village random tree, with only the best village printed:

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 200000;                         // worst case, built here
    mt19937 rng(38);
    vector<vector<int>> adj(n + 1);
    for (int v = 2; v <= n; v++) {          // a random tree
        int p = rng() % (v - 1) + 1;
        adj[p].push_back(v);
        adj[v].push_back(p);
    }
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<ll> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {           // pass 2: parents before children
        int v = order[i], p = par[v];
        ans[v] = ans[p] - sz[v] + (n - sz[v]);   // move the shop from p to v
    }
    int best = min_element(ans.begin() + 1, ans.end()) - ans.begin();
    cout << "best village " << best << ", total " << ans[best] << "\n";
    return 0;
}

Output: best village 2, total 2386967, in a few hundredths of a second.

A stress test

A BFS from every village vs rerooting, on 1000 random trees of up to 12 villages:

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

vector<ll> brute(int n, vector<vector<int>>& adj) {
    vector<ll> res(n + 1);
    for (int s = 1; s <= n; s++) {
        vector<int> dist(n + 1, -1);
        queue<int> q;
        q.push(s);
        dist[s] = 0;
        while (!q.empty()) {
            int v = q.front(); q.pop();
            res[s] += dist[v];
            for (int u : adj[v]) if (dist[u] == -1) { dist[u] = dist[v] + 1; q.push(u); }
        }
    }
    return res;
}
vector<ll> fast(int n, vector<vector<int>>& adj) {
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<ll> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {           // pass 2: parents before children
        int v = order[i], p = par[v];
        ans[v] = ans[p] - sz[v] + (n - sz[v]);   // move the shop from p to v
    }
    return ans;
}
int main() {
    mt19937 rng(38);
    for (int t = 1; t <= 1000; t++) {
        int n = rng() % 12 + 1;
        vector<vector<int>> adj(n + 1);
        for (int v = 2; v <= n; v++) {
            int p = rng() % (v - 1) + 1;
            adj[p].push_back(v);
            adj[v].push_back(p);
        }
        if (brute(n, adj) != fast(n, adj)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 1000 tests passed";
}

Output: all 1000 tests passed.

One more tree DP: festival stalls

Village v has w[v] volunteers. Choose villages to host a stall so that no two neighbouring villages both host; maximise the total volunteers. (This is the maximum-weight independent set on a tree.)

A child's choice depends only on whether its parent hosts, so each village keeps two answers:

  • dp[v][0] = best total in v's subtree when v does not host = Σ max(dp[c][0], dp[c][1]);
  • dp[v][1] = best total when v hosts = w[v] + Σ dp[c][0].

Answer: max(dp[root][0], dp[root][1]).

#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<ll> w(n + 1);
    for (int v = 1; v <= n; v++) cin >> w[v];
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    // dp[v][0]: best in v's subtree, no stall at v · dp[v][1]: stall at v
    vector<array<ll, 2>> dp(n + 1);
    for (int i = n - 1; i >= 0; i--) {
        int v = order[i];
        dp[v][1] += w[v];
        if (i > 0) {
            int p = par[v];
            dp[p][0] += max(dp[v][0], dp[v][1]);   // p free: v may host or not
            dp[p][1] += dp[v][0];                   // p hosts: v must not
        }
    }
    cout << max(dp[1][0], dp[1][1]) << "\n";
    return 0;
}

Input 5 / 1 5 3 4 2 / edges 1-2 1-3 2-4 2-5 prints 9: villages 3, 4 and 5 host (3 + 4 + 2). Greedy "biggest village first" picks village 2 (5), then only village 3 is allowed: 8.

Complexity vs the constraints

Approach Time Memory Verdict
BFS from every village O(n²) = 4 · 10^10 O(n) TLE
tree DP + rerooting O(n): two passes O(n) accepted

Common mistakes (and the real outputs)

Bug 1: recursion on a deep tree

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

int n;
vector<vector<int>> adj;
vector<ll> sz, down;

void dfs(int v, int p) {                  // recursive tree DP
    for (int u : adj[v])
        if (u != p) {
            dfs(u, v);
            sz[v] += sz[u];
            down[v] += down[u] + sz[u];
        }
}

int main() {
    n = 200000;                             // a straight road: 1 - 2 - ... - n
    adj.resize(n + 1);
    for (int v = 2; v <= n; v++) {
        adj[v - 1].push_back(v);
        adj[v].push_back(v - 1);
    }
    sz.assign(n + 1, 1);
    down.assign(n + 1, 0);
    dfs(1, 0);
    cout << "village 1: " << down[1] << "\n";
    return 0;
}

On a straight road of 2 · 10^5 villages the recursion is 2 · 10^5 calls deep: Runtime Error (SIGSEGV), a stack overflow. Codeforces gives a large stack, but many judges (and this compiler) use about 8 MB. A BFS order and two loops never overflow.

Bug 2: int for distance sums

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n = 200000;                         // a straight road: 1 - 2 - ... - n
    vector<vector<int>> adj(n + 1);
    for (int v = 2; v <= n; v++) {
        adj[v - 1].push_back(v);
        adj[v].push_back(v - 1);
    }
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<int> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {           // pass 2: parents before children
        int v = order[i], p = par[v];
        ans[v] = ans[p] - sz[v] + (n - sz[v]);   // move the shop from p to v
    }
    int best = min_element(ans.begin() + 1, ans.end()) - ans.begin();
    cout << "best village " << best << ", total " << ans[best] << "\n";
    return 0;
}

Prints best village 72845, total -2147480708. With long long the same program prints best village 100000, total 10000000000: ten billion, far above the int limit of about 2.1 · 10^9. On a path the sums grow like n²/4.

Bug 3: the signs swapped

#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<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<ll> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {           // pass 2: parents before children
        int v = order[i], p = par[v];
        ans[v] = ans[p] + sz[v] - (n - sz[v]);   // move the shop from p to v
    }
    for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
    return 0;
}

Sample 1 prints 9 5 11 7 9 5: village 1 (from the tree DP) is right, every rerooted answer is wrong. The villages below the new shop walk less, so sz[c] is subtracted.

Summary table

Mistake What you see Why Fix
recursive DFS, depth 2 · 10^5 Runtime Error (SIGSEGV) stack overflow BFS order + two loops
vector<int> sums -2147480708 sums reach ~n²/4 = 10^10 long long
ans[p] + sz[v] − (n − sz[v]) 9 5 11 7 9 5 signs swapped ans[p] − sz[v] + (n − sz[v])
a BFS from every village Time Limit Exceeded O(n²) reroot in O(1) per edge
par check missing in the BFS infinite loop / wrong order walks back to the parent if (u != par[v])

Mini project

Build a "best facility" tool for a tree with weighted roads and village populations: the cost of a spot is Σ population[u] · dist(u, v). Generalise sz to "population in the subtree" and the reroot formula to ans[c] = ans[p] + w(p, c) · (total − 2 · pop[c]). Print the best village and its cost, and check against a Dijkstra-free brute force (one DFS per village) for n ≤ 200.

Practice

  1. For every village, the distance to the farthest village (unit roads).

    Answer Rerooting with two values: down1[v] = deepest path into v's subtree, and up[v] = longest path that leaves v's subtree through its parent. For each child c, up[c] = 1 + max(up[p], best down among p's other children + 1); keep the top two child depths of p to exclude c. Answer max(down1[v], up[v]). Sample 1: <b>3 4 2 3 3 4</b>.

  2. Weighted roads (lengths up to 10^9).

    Answer down[p] += down[c] + w · sz[c]; ans[c] = ans[p] + w · (n − 2 · sz[c]). Use long long: totals reach about n² · 10^9 / 4 ≈ 10^19 in the worst case, so check the limits (use __int128 or unsigned if needed).

  3. Count the valid stall plans mod 10^9 + 7.

    Answer Same states with counts: c0[v] = Π (c0[c] + c1[c]), c1[v] = Π c0[c]; answer c0[1] + c1[1]. For the 5-village example: <b>14</b> (this includes the empty plan).

  4. The root that maximises Σ sz[v] (the sum of subtree sizes).

    Answer Σ sz[v] when rooted at r equals Σ (dist(r, v) + 1) = ans[r] + n, so it is the village with the largest rerooting answer. Sample 1: village 2 or 6 (13 + 6 = <b>19</b>).

Quick quiz

n = 10, ans[p] = 30, c is a child of p with sz[c] = 3. What is ans[c]?

A) 26 · B) 34 · C) 27 · D) 33

Answer

B. 30 − 3 + (10 − 3) = 34: three villages walk one road less, seven walk one road more.

Interview questions

  1. What is DP on a tree? Root the tree, define a value per subtree, and compute it from the children's values (leaves first).
  2. How do you process a tree without recursion? BFS (or an explicit stack) from the root gives an order with parents before children; loop over it backwards for bottom-up values and forwards for top-down values.
  3. What is rerooting? Computing an answer for every root: one tree DP for a fixed root, then a top-down pass that moves the root one edge at a time with an O(1) (or O(degree)) adjustment.
  4. Sum of distances from every vertex in O(n)? sz and down bottom-up; ans[c] = ans[p] − sz[c] + (n − sz[c]) top-down.
  5. Why can recursive DFS fail? Recursion depth equals tree height, up to n; 2 · 10^5 frames can overflow an 8 MB stack.
  6. Maximum independent set on a tree? dp[v][0/1] (v excluded/included): O(n), although it is NP-hard on general graphs.

Glossary

Term Meaning Example
Tree A connected graph with n vertices and n − 1 edges (no cycles) 6 villages, 5 roads
Root The vertex the tree hangs from village 1
Parent / child Neighbours one step towards / away from the root 3 is the parent of 5
Leaf A vertex with no children 2, 4, 6
Subtree A vertex and everything below it subtree of 3 = {3, 4, 5, 6}
Tree DP DP whose states are subtrees, computed from the children sz, down
BFS order Vertices listed by a breadth-first search; parents before children 1 2 3 4 5 6
Rerooting Moving the root one edge at a time to get every root's answer ans[3] = 9 − 4 + 2
Independent set Vertices with no two adjacent {3, 4, 5}
Stack overflow Too-deep recursion exhausts the call stack SIGSEGV at depth 2 · 10^5
Integer overflow A value exceeds its type's range and wraps -2147480708

Summary

  • A BFS from every vertex is O(n²): TLE at 2 · 10^5.
  • Root the tree; build subtree values from the children: sz[v] = 1 + Σ sz[c], down[v] = Σ (down[c] + sz[c]).
  • Reroot: ans[c] = ans[p] − sz[c] + (n − sz[c]), parents before children. Total O(n).
  • Use a BFS order instead of recursion, and long long for distance sums.
  • Two answers per vertex (dp[v][0/1]) solve "choose vertices, no two neighbours".
  • Real bugs: SIGSEGV from recursion, -2147480708 from int, 9 5 11 7 9 5 from swapped signs.

Solutions in C++, Java and Python

Problem O · Ration Shop

C++

#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<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    // BFS order from village 1: every parent comes before its children
    vector<int> order = {1}, par(n + 1, 0);
    for (int i = 0; i < (int)order.size(); i++)
        for (int u : adj[order[i]])
            if (u != par[order[i]]) { par[u] = order[i]; order.push_back(u); }
    vector<ll> sz(n + 1, 1), down(n + 1, 0), ans(n + 1);
    for (int i = n - 1; i > 0; i--) {       // pass 1: children before parents
        int v = order[i], p = par[v];
        sz[p] += sz[v];
        down[p] += down[v] + sz[v];          // everyone below v walks one more road
    }
    ans[1] = down[1];
    for (int i = 1; i < n; i++) {           // pass 2: parents before children
        int v = order[i], p = par[v];
        ans[v] = ans[p] - sz[v] + (n - sz[v]);   // move the shop from p to v
    }
    for (int v = 1; v <= n; v++) cout << ans[v] << " \n"[v == n];
    return 0;
}

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        DataInputStream in = new DataInputStream(new BufferedInputStream(System.in, 1 << 16));
        int n = nextInt(in);
        int[] head = new int[n + 1], nxt = new int[2 * (n - 1)], to = new int[2 * (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++;
        }
        // BFS order from village 1: every parent comes before its children
        int[] order = new int[n], par = new int[n + 1];
        order[0] = 1;
        for (int i = 0, cnt = 1; i < cnt; i++) {
            int v = order[i];
            for (int e = head[v]; e != -1; e = nxt[e])
                if (to[e] != par[v]) { par[to[e]] = v; order[cnt++] = to[e]; }
        }
        long[] sz = new long[n + 1], down = new long[n + 1], ans = new long[n + 1];
        Arrays.fill(sz, 1);
        for (int i = n - 1; i > 0; i--) {          // pass 1: children before parents
            int v = order[i], p = par[v];
            sz[p] += sz[v];
            down[p] += down[v] + sz[v];
        }
        ans[1] = down[1];
        for (int i = 1; i < n; i++) {              // pass 2: parents before children
            int v = order[i], p = par[v];
            ans[v] = ans[p] - sz[v] + (n - sz[v]);
        }
        StringBuilder sb = new StringBuilder();
        for (int v = 1; v <= n; v++) sb.append(ans[v]).append(v == n ? "\n" : " ");
        System.out.print(sb);
    }

    static int nextInt(DataInputStream in) throws IOException {
        int r = 0, b = in.read();
        while (b < '0') b = in.read();
        while (b >= '0') { r = r * 10 + (b - '0'); b = in.read(); }
        return r;
    }
}

Python (iterative, so no recursion limit; fine for n = 2 · 10^5)

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    adj = [[] for _ in range(n + 1)]
    for i in range(n - 1):
        a, b = int(data[1 + 2 * i]), int(data[2 + 2 * i])
        adj[a].append(b)
        adj[b].append(a)
    # BFS order from village 1: every parent comes before its children
    order, par = [1], [0] * (n + 1)
    for v in order:                      # the list grows while we walk it
        for u in adj[v]:
            if u != par[v]:
                par[u] = v
                order.append(u)
    sz, down, ans = [1] * (n + 1), [0] * (n + 1), [0] * (n + 1)
    for v in reversed(order[1:]):        # pass 1: children before parents
        p = par[v]
        sz[p] += sz[v]
        down[p] += down[v] + sz[v]
    ans[1] = down[1]
    for v in order[1:]:                  # pass 2: parents before children
        ans[v] = ans[par[v]] - sz[v] + (n - sz[v])
    print(" ".join(map(str, ans[1:])))

main()

All three print 9 13 7 11 9 13 for sample 1 and 0 for a single village.

Next episode: DP 8: SOS DP (sum over subsets): for every bitmask, add up the values of all its submasks.