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
-
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>. -
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). -
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). -
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
- What is DP on a tree? Root the tree, define a value per subtree, and compute it from the children's values (leaves first).
- 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.
- 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.
- 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.
- Why can recursive DFS fail? Recursion depth equals tree height, up to n; 2 · 10^5 frames can overflow an 8 MB stack.
- 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 longfor distance sums. - Two answers per vertex (
dp[v][0/1]) solve "choose vertices, no two neighbours". - Real bugs: SIGSEGV from recursion,
-2147480708fromint,9 5 11 7 9 5from 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.