Every tree so far had a root and two children. Judges give you n − 1 edges. This deck is the nine moves that turn an edge list into answers, across fifteen problems.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the problem's fixed number in this deck, not a slide position.
A general tree arrives as n − 1 edges, with no parent marked. Store each edge in both endpoints' lists and walk from a chosen root, skipping only the parent.
A tree with n nodes arrives as n − 1 undirected edges, and each edge is stored in both endpoints' lists. How many entries do the lists hold in total?
Each of the n − 1 edges is stored twice, so 2(n − 1) entries.
A DFS skips the parent with if (to == parent) continue; and keeps no visited array. On which input does it never finish?
In a tree the only visited neighbour is the parent. A graph with a cycle never finishes.
GIVEN · ASKEDGiven n employees 0 … n − 1, manager[i] (−1 for the head, headID) and informTime[i], the minutes i needs to tell their direct reports. Return the minutes until everyone knows.
“manager[i] is the direct manager of employee i.” A parent array is a tree that is already rooted, with every edge already pointing one way.
Managers tell all reports at once, so branches run in parallel. The answer is the costliest root-to-leaf path. Turn the parent array into children lists first.
// Parent array -> children lists, then the costliest root-to-leaf path. vector<vector<int>> kids; int dfs(int v, vector<int>& informTime) { int longest = 0; for (int c : kids[v]) longest = max(longest, dfs(c, informTime)); return informTime[v] + longest; // v's minutes, then the slowest branch } int numOfMinutes(int n, int headID, vector<int>& manager, vector<int>& informTime) { kids.assign(n, vector<int>()); for (int v = 0; v < n; v++) if (manager[v] != -1) kids[manager[v]].push_back(v); return dfs(headID, informTime); }
// Parent array -> children lists, then the costliest root-to-leaf path. List<List<Integer>> kids = new ArrayList<>(); int dfs(int v, int[] informTime) { int longest = 0; for (int c : kids.get(v)) longest = Math.max(longest, dfs(c, informTime)); return informTime[v] + longest; // v's minutes, then the slowest branch } public int numOfMinutes(int n, int headID, int[] manager, int[] informTime) { for (int i = 0; i < n; i++) kids.add(new ArrayList<>()); for (int v = 0; v < n; v++) if (manager[v] != -1) kids.get(manager[v]).add(v); return dfs(headID, informTime); }
# Parent array -> children lists, then the latest arrival of the news. def numOfMinutes(n, headID, manager, informTime): kids = [[] for _ in range(n)] for v, m in enumerate(manager): if m != -1: kids[m].append(v) latest, stack = 0, [(headID, 0)] # (employee, minute the news arrives) while stack: v, t = stack.pop() latest = max(latest, t) for c in kids[v]: stack.append((c, t + informTime[v])) return latest
Adding children's times. Branches run at the same time: take the largest, not the sum.
GIVEN · ASKEDA tree rooted at vertex 1, Kefa's home. Some vertices hold a cat. Every leaf is a restaurant. Count the restaurants whose path from home never has more than m cat vertices in a row.
A tree rooted at vertex 1, given as n − 1 undirected edges, with a condition on the path from the root down to each leaf.
The rule is about the path from the root, so carry it down: the run of cats ending here. Past m, cut the subtree off.
#include <bits/stdc++.h> using namespace std; int n, m, answer = 0; int cat[100005]; vector<int> adj[100005]; void dfs(int v, int parent, int streak) { streak = cat[v] ? streak + 1 : 0; // cats in a row, ending at v if (streak > m) return; // nothing below v can be reached bool leaf = true; for (int to : adj[v]) { if (to == parent) continue; leaf = false; dfs(to, v, streak); } if (leaf) answer++; // no neighbour except the parent } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; for (int v = 1; v <= n; v++) cin >> cat[v]; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0, 0); cout << answer << "\n"; }
import sys def main(): data = sys.stdin.buffer.read().split() n, m = int(data[0]), int(data[1]) cat = [0] + [int(x) for x in data[2:2 + n]] adj = [[] for _ in range(n + 1)] pos = 2 + n for _ in range(n - 1): a, b = int(data[pos]), int(data[pos + 1]); pos += 2 adj[a].append(b); adj[b].append(a) answer, stack = 0, [(1, 0, 0)] # (vertex, parent, run of cats above it) while stack: v, parent, streak = stack.pop() streak = streak + 1 if cat[v] else 0 if streak > m: continue # nothing below v can be reached leaf = True for to in adj[v]: if to != parent: leaf = False stack.append((to, v, streak)) if leaf: answer += 1 # no neighbour except the parent print(answer) main()
Leaf test adj[v].size() == 1. The root also has one neighbour with a single child.
Deck 2's postorder with a loop over the children. A node counts itself and adds each child's size; it is final only after the last child reports.
A root has three children whose subtrees hold 4, 1 and 2 nodes. What is sz[root], and how many subordinates does the root have?
sz counts the node itself, so it is 1 + 4 + 1 + 2 = 8.
GIVEN · ASKEDEmployee 1 is the director. Given the direct boss of each employee 2 … n, print for each employee how many people are below them.
“For each employee, count the subordinates.” An answer for every node, where each answer covers the node's whole subtree.
Size = 1 + the children's sizes, in one postorder. Subordinates = size − 1.
#include <bits/stdc++.h> using namespace std; vector<int> kids[200005]; int sz[200005]; void dfs(int v) { sz[v] = 1; // v counts itself for (int c : kids[v]) { dfs(c); sz[v] += sz[c]; // plus what each child hands up } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int v = 2; v <= n; v++) { int boss; cin >> boss; kids[boss].push_back(v); } dfs(1); for (int v = 1; v <= n; v++) cout << sz[v] - 1 << " "; cout << "\n"; }
import sys def main(): data = sys.stdin.buffer.read().split() n = int(data[0]) boss = [0, 0] + [int(x) for x in data[1:n]] kids = [[] for _ in range(n + 1)] for v in range(2, n + 1): kids[boss[v]].append(v) order, stack = [], [1] while stack: # parents come out before children v = stack.pop(); order.append(v) stack.extend(kids[v]) sz = [1] * (n + 1) # every employee counts themself for v in reversed(order): # so backwards is children first if v != 1: sz[boss[v]] += sz[v] print(' '.join(str(sz[v] - 1) for v in range(1, n + 1))) main()
A separate walk per employee. On a chain that is 2·10¹⁰ steps.
GIVEN · ASKEDA tree on nodes 0 … n − 1, hasApple[v], 1 second per edge. Return the fewest seconds to start at 0, collect every apple and return to 0.
“Start at vertex 0, collect every apple, and come back to vertex 0.” A walk that returns to its start crosses each edge it uses exactly twice.
An edge is worth walking only if an apple lies below it. The parent adds 2 for each child whose subtree holds an apple.
// Each edge that leads to an apple is walked down and back: 2 seconds. vector<vector<int>> adj; int dfs(int v, int parent, vector<bool>& hasApple) { int cost = 0; // seconds spent inside v's subtree for (int to : adj[v]) { if (to == parent) continue; int below = dfs(to, v, hasApple); if (below > 0 || hasApple[to]) // an apple at `to` or under it cost += below + 2; } return cost; } int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) { adj.assign(n, vector<int>()); for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); } return dfs(0, -1, hasApple); }
// Each edge that leads to an apple is walked down and back: 2 seconds. List<List<Integer>> adj = new ArrayList<>(); int dfs(int v, int parent, List<Boolean> hasApple) { int cost = 0; // seconds spent inside v's subtree for (int to : adj.get(v)) { if (to == parent) continue; int below = dfs(to, v, hasApple); if (below > 0 || hasApple.get(to)) // an apple at `to` or under it cost += below + 2; } return cost; } public int minTime(int n, int[][] edges, List<Boolean> hasApple) { for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } return dfs(0, -1, hasApple); }
# Each edge that leads to an apple is walked down and back: 2 seconds. def minTime(n, edges, hasApple): adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b); adj[b].append(a) parent, order, stack = [-1] * n, [], [0] while stack: # parents come out before children v = stack.pop(); order.append(v) for to in adj[v]: if to != parent[v]: parent[to] = v; stack.append(to) cost = [0] * n # seconds spent inside v's subtree need = list(hasApple) # does v's subtree hold an apple? for v in reversed(order): # children before parents p = parent[v] if p != -1 and need[v]: cost[p] += cost[v] + 2 need[p] = True return cost[0]
Trusting the order inside an edge. [a, b] does not say a is the parent. Add both directions.
In Minimum Time to Collect All Apples, what does a child hand up to its parent?
The parent needs seconds, so each child reports the seconds inside its own subtree.
A path can use only two of a node's children. Keep the two longest arms: their sum is the best path turning here, and the longest is what the node returns.
A node's three children return 2, 5 and 4. What path does the node score through itself, and what does it return to its parent?
Each arm is the child's return plus the edge to that child, so the arms are 3, 6 and 5.
Why can a node not return best1 + best2 to its parent?
A path passes a node once, so it uses at most two of its edges.
GIVEN · ASKEDA tree as n − 1 edges. Print the most edges on a path between two nodes.
“The maximum distance between two nodes.” The longest path in a tree, with no root given and any number of children per node.
Root it anywhere. Every path turns at its highest node and goes down two arms into two different children.
#include <bits/stdc++.h> using namespace std; vector<int> adj[200005]; int diameter = 0; int dfs(int v, int parent) { // the longest arm below v, in edges int best1 = 0, best2 = 0; for (int to : adj[v]) { if (to == parent) continue; int d = dfs(to, v) + 1; // the arm through this child if (d > best1) { best2 = best1; best1 = d; } else if (d > best2) best2 = d; } diameter = max(diameter, best1 + best2); return best1; // a parent can use only one arm } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0); cout << diameter << "\n"; }
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) parent, order, stack = [0] * (n + 1), [], [1] while stack: # parents come out before children v = stack.pop(); order.append(v) for to in adj[v]: if to != parent[v]: parent[to] = v; stack.append(to) best1, best2 = [0] * (n + 1), [0] * (n + 1) # two longest arms below v for v in reversed(order): # children before parents d, p = best1[v] + 1, parent[v] # the arm v offers its parent if d > best1[p]: best1[p], best2[p] = d, best1[p] elif d > best2[p]: best2[p] = d print(max(best1[v] + best2[v] for v in range(1, n + 1))) main()
Keeping only the longest arm. The second longest is thrown away and the answer comes out short.
GIVEN · ASKEDparent[] with root 0 and a letter s[v] on each node. Return the most nodes on a path where neighbouring nodes have different letters.
“The longest path such that no pair of adjacent nodes has the same character.” A diameter, with a rule about which arms may join.
Problem 5 with one filter: a child's chain extends through its parent only if their letters differ. Count in nodes.
// Diameter with a filter: a chain may pass through v only if the letters differ. vector<vector<int>> kids; int best; int dfs(int v, string& s) { // longest valid chain down from v, in nodes int best1 = 0, best2 = 0; for (int c : kids[v]) { int len = dfs(c, s); // always recurse: the answer may lie below if (s[c] == s[v]) continue; // same letter: this chain stops at c if (len > best1) { best2 = best1; best1 = len; } else if (len > best2) best2 = len; } best = max(best, best1 + best2 + 1); // the two chains, joined at v return best1 + 1; } int longestPath(vector<int>& parent, string s) { int n = parent.size(); kids.assign(n, vector<int>()); best = 1; for (int v = 1; v < n; v++) kids[parent[v]].push_back(v); dfs(0, s); return best; }
// Diameter with a filter: a chain may pass through v only if the letters differ. List<List<Integer>> kids = new ArrayList<>(); int best = 1; int dfs(int v, String s) { // longest valid chain down from v, in nodes int best1 = 0, best2 = 0; for (int c : kids.get(v)) { int len = dfs(c, s); // always recurse: the answer may lie below if (s.charAt(c) == s.charAt(v)) continue; if (len > best1) { best2 = best1; best1 = len; } else if (len > best2) best2 = len; } best = Math.max(best, best1 + best2 + 1); return best1 + 1; } public int longestPath(int[] parent, String s) { int n = parent.length; for (int i = 0; i < n; i++) kids.add(new ArrayList<>()); for (int v = 1; v < n; v++) kids.get(parent[v]).add(v); dfs(0, s); return best; }
# Diameter with a filter: a chain may pass through v only if the letters differ. def longestPath(parent, s): n = len(parent) kids = [[] for _ in range(n)] for v in range(1, n): kids[parent[v]].append(v) order, stack = [], [0] while stack: # parents come out before children v = stack.pop(); order.append(v) stack.extend(kids[v]) best1, best2 = [0] * n, [0] * n # two longest valid chains below v best = 1 for v in reversed(order): # children before parents best = max(best, best1[v] + best2[v] + 1) p = parent[v] if p != -1 and s[p] != s[v]: # v's chain may pass through p length = best1[v] + 1 if length > best1[p]: best1[p], best2[p] = length, best1[p] elif length > best2[p]: best2[p] = length return best
Skipping the call when letters match. Always recurse; only the use of the result is filtered.
Remove every leaf at once, then the new leaves, round after round. The one or two nodes left are the centres, the middle of every longest path.
How many centres can a tree have?
The centres are the middle of a longest path: one node for an even length, two for an odd one. Never more than two.
The path 0 – 1 – 2 – 3 – 4 – 5 is peeled in rounds. Which nodes are returned?
Round 1 removes 0 and 5, round 2 removes 1 and 4. Left: 2 and 3.
GIVEN · ASKEDA tree on nodes 0 … n − 1. Return every node that gives the smallest height when used as the root.
“Choose the root that gives the smallest height.” The tree is unrooted and the question is about its middle.
The best roots are the middle of a longest path. Peel all leaves at once, round after round; the last one or two nodes are the centres.
// Peel the leaves in rounds; the last one or two nodes are the centres. vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { if (n == 1) return {0}; vector<vector<int>> adj(n); vector<int> deg(n, 0), leaves; for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); deg[e[0]]++; deg[e[1]]++; } for (int v = 0; v < n; v++) if (deg[v] == 1) leaves.push_back(v); int left = n; while (left > 2) { // a tree has 1 or 2 centres left -= leaves.size(); vector<int> next; for (int v : leaves) for (int to : adj[v]) if (--deg[to] == 1) next.push_back(to); // subtract, then test leaves = next; } return leaves; }
// Peel the leaves in rounds; the last one or two nodes are the centres. public List<Integer> findMinHeightTrees(int n, int[][] edges) { if (n == 1) return Arrays.asList(0); List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); int[] deg = new int[n]; for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); deg[e[0]]++; deg[e[1]]++; } List<Integer> leaves = new ArrayList<>(); for (int v = 0; v < n; v++) if (deg[v] == 1) leaves.add(v); int left = n; while (left > 2) { // a tree has 1 or 2 centres left -= leaves.size(); List<Integer> next = new ArrayList<>(); for (int v : leaves) for (int to : adj.get(v)) if (--deg[to] == 1) next.add(to); // subtract, then test leaves = next; } return leaves; }
# Peel the leaves in rounds; the last one or two nodes are the centres. def findMinHeightTrees(n, edges): if n == 1: return [0] adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b); adj[b].append(a) deg = [len(x) for x in adj] leaves = [v for v in range(n) if deg[v] == 1] left = n while left > 2: # a tree has 1 or 2 centres left -= len(leaves) nxt = [] for v in leaves: for to in adj[v]: deg[to] -= 1 if deg[to] == 1: # a new leaf nxt.append(to) leaves = nxt return leaves
Stopping mid-round. Finish each round before checking the count, and handle n = 1 first.
GIVEN · ASKEDcoins[v] is 0 or 1. Standing on a node you collect every coin within 2 edges. Return the fewest edge moves to collect all coins and end where you began; you choose the start.
“Collect all coins within distance 2”, then return. You choose the start.
Trim leaves with no coin until every leaf has one. Then remove all leaves twice: those coins are within 2. Every edge left is walked out and back.
// Trim coinless leaves, drop two more layers, walk what is left twice. int collectCoins(vector<int>& coins, vector<vector<int>>& edges) { int n = coins.size(); vector<vector<int>> adj(n); vector<int> deg(n, 0); for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); deg[e[0]]++; deg[e[1]]++; } vector<bool> gone(n, false); queue<int> q; for (int v = 0; v < n; v++) if (deg[v] == 1 && !coins[v]) q.push(v); while (!q.empty()) { // 1. a leaf with no coin is never visited int v = q.front(); q.pop(); gone[v] = true; for (int to : adj[v]) if (!gone[to] && --deg[to] == 1 && !coins[to]) q.push(to); } for (int round = 0; round < 2; round++) { // 2. coins are reached from 2 edges away vector<int> leaves; for (int v = 0; v < n; v++) if (!gone[v] && deg[v] == 1) leaves.push_back(v); for (int v : leaves) { gone[v] = true; for (int to : adj[v]) if (!gone[to]) deg[to]--; } } int kept = 0; // 3. each surviving edge: out and back for (auto& e : edges) if (!gone[e[0]] && !gone[e[1]]) kept++; return 2 * kept; }
// Trim coinless leaves, drop two more layers, walk what is left twice. public int collectCoins(int[] coins, int[][] edges) { int n = coins.length; List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); int[] deg = new int[n]; for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); deg[e[0]]++; deg[e[1]]++; } boolean[] gone = new boolean[n]; Deque<Integer> q = new ArrayDeque<>(); for (int v = 0; v < n; v++) if (deg[v] == 1 && coins[v] == 0) q.add(v); while (!q.isEmpty()) { // 1. a leaf with no coin is never visited int v = q.poll(); gone[v] = true; for (int to : adj.get(v)) if (!gone[to] && --deg[to] == 1 && coins[to] == 0) q.add(to); } for (int round = 0; round < 2; round++) { // 2. coins are reached from 2 edges away List<Integer> leaves = new ArrayList<>(); for (int v = 0; v < n; v++) if (!gone[v] && deg[v] == 1) leaves.add(v); for (int v : leaves) { gone[v] = true; for (int to : adj.get(v)) if (!gone[to]) deg[to]--; } } int kept = 0; // 3. each surviving edge: out and back for (int[] e : edges) if (!gone[e[0]] && !gone[e[1]]) kept++; return 2 * kept; }
# Trim coinless leaves, drop two more layers, walk what is left twice. from collections import deque def collectCoins(coins, edges): n = len(coins) adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b); adj[b].append(a) deg = [len(x) for x in adj] gone = [False] * n q = deque(v for v in range(n) if deg[v] == 1 and not coins[v]) while q: # 1. a leaf with no coin is never visited v = q.popleft() gone[v] = True for to in adj[v]: if not gone[to]: deg[to] -= 1 if deg[to] == 1 and not coins[to]: q.append(to) for _ in range(2): # 2. coins are reached from 2 edges away leaves = [v for v in range(n) if not gone[v] and deg[v] == 1] for v in leaves: gone[v] = True for to in adj[v]: if not gone[to]: deg[to] -= 1 kept = sum(1 for a, b in edges if not gone[a] and not gone[b]) return 2 * kept # 3. each surviving edge: out and back
Mixing the two phases. Trimming runs until no coinless leaf is left; then exactly two rounds remove every leaf.
Each node hands up a pair: skip (it stays free) and take (matched to one child). The parent needs to know if a child is still free.
A node v has two children, both leaves. What are skip[v] and take[v] in Tree Matching?
Leaves hand up (0, 0). If v stays free, no edge is chosen below it and skip is 0.
Why does take[v] use skip[c] for the chosen child c, and not max(skip[c], take[c])?
Choosing v–c makes c an endpoint. If c were also matched below, it would be used twice.
GIVEN · ASKEDA tree as n − 1 edges. Print the most edges you can choose so that no node is on two of them.
“The most edges with no node used twice.” Choosing an edge blocks its neighbours, like House Robber.
Each node hands up two: skip (left free) and take (matched to one child). Matching v to c needs c free below and adds 1.
#include <bits/stdc++.h> using namespace std; vector<int> adj[200005]; int skip[200005], take[200005]; // v left free / v matched to a child void dfs(int v, int parent) { for (int to : adj[v]) { if (to == parent) continue; dfs(to, v); skip[v] += max(skip[to], take[to]); // v free: each child does its best } for (int to : adj[v]) { if (to == parent) continue; // match v with this child: int rest = skip[v] - max(skip[to], take[to]); // the other children, unchanged take[v] = max(take[v], rest + skip[to] + 1); // `to` must be free below } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0); cout << max(skip[1], take[1]) << "\n"; }
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) parent, order, stack = [0] * (n + 1), [], [1] while stack: # parents come out before children v = stack.pop(); order.append(v) for to in adj[v]: if to != parent[v]: parent[to] = v; stack.append(to) skip, take = [0] * (n + 1), [0] * (n + 1) # v left free / v matched to a child for v in reversed(order): # children before parents for to in adj[v]: if to != parent[v]: skip[v] += max(skip[to], take[to]) for to in adj[v]: if to != parent[v]: # match v with this child rest = skip[v] - max(skip[to], take[to]) take[v] = max(take[v], rest + skip[to] + 1) print(max(skip[1], take[1])) main()
Recomputing the other children's sum for each c. On a star that is quadratic.
GIVEN · ASKEDEach vertex v picks a value av in its own range [lv, rv]. Print the largest possible sum of |au − av| over the edges.
A choice at every node that affects only its neighbours, and a score summed over the edges.
Some best answer puts every value at l or r. So each node has two states and hands up two numbers; the parent tries both for each child.
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n; ll lo[100005], hi[100005], dpLo[100005], dpHi[100005]; vector<int> adj[100005]; void dfs(int v, int parent) { dpLo[v] = dpHi[v] = 0; for (int to : adj[v]) { if (to == parent) continue; dfs(to, v); // the child tries both of its ends dpLo[v] += max(dpLo[to] + abs(lo[v] - lo[to]), dpHi[to] + abs(lo[v] - hi[to])); dpHi[v] += max(dpLo[to] + abs(hi[v] - lo[to]), dpHi[to] + abs(hi[v] - hi[to])); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { cin >> n; for (int v = 1; v <= n; v++) { cin >> lo[v] >> hi[v]; adj[v].clear(); } for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0); cout << max(dpLo[1], dpHi[1]) << "\n"; } }
import sys def main(): data = sys.stdin.buffer.read().split() pos, out = 1, [] for _ in range(int(data[0])): n = int(data[pos]); pos += 1 lo, hi = [0] * (n + 1), [0] * (n + 1) for v in range(1, n + 1): lo[v], hi[v] = int(data[pos]), int(data[pos + 1]); pos += 2 adj = [[] for _ in range(n + 1)] for _ in range(n - 1): a, b = int(data[pos]), int(data[pos + 1]); pos += 2 adj[a].append(b); adj[b].append(a) parent, order, stack = [0] * (n + 1), [], [1] while stack: # parents come out before children v = stack.pop(); order.append(v) for to in adj[v]: if to != parent[v]: parent[to] = v; stack.append(to) dp_lo, dp_hi = [0] * (n + 1), [0] * (n + 1) for v in reversed(order): # children before parents p = parent[v] if p: # v tries both of its ends for each end of p dp_lo[p] += max(dp_lo[v] + abs(lo[p] - lo[v]), dp_hi[v] + abs(lo[p] - hi[v])) dp_hi[p] += max(dp_lo[v] + abs(hi[p] - lo[v]), dp_hi[v] + abs(hi[p] - hi[v])) out.append(max(dp_lo[1], dp_hi[1])) print('\n'.join(map(str, out))) main()
Using int. The total overflows 32 bits.
A DFS finishes a subtree before leaving it, so in entry order each subtree is one unbroken block, from tin to just before tout.
tin[v] = 4 and tout[v] = 9, where tout is the clock after the last descendant. How many nodes are in the subtree of v?
Positions 4 to 8, so 5 nodes in the subtree: v and 4 descendants.
With entry and exit times stored, how do we test whether a is an ancestor of b?
b is in a's subtree when b's block sits inside a's block. Two comparisons, O(1).
The next problem changes one cell and sums a prefix, many times. A Fenwick tree does both in
O(log n). bit[i] holds the sum of the last i & -i cells ending at
cell i, cells counted from 1. i & -i is the lowest 1 in the binary form of i.
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| i & -i | 1 | 2 | 1 | 4 | 1 | 2 | 1 | 8 |
prefix(7) = bit[7] + bit[6] + bit[4]: subtract the lowest 1 each time, 7, 6, 4, 0.
add at cell 3 touches bit[3], bit[4], bit[8]: add the lowest 1 each time, 3, 4, 8.
Both loops take at most log n steps, because each one changes the lowest 1 of i.
GIVEN · ASKEDA tree rooted at 1 with a value on each node. Two operations: set the value of node s to x, or print the sum over the subtree of s.
Updates mixed with subtree sums, so the sums can't be computed once.
Write nodes in DFS entry order: a subtree is the block tin[v] to tout[v] − 1. Point update and range sum on a Fenwick tree, O(log n).
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 200005; int n, q, timer = 0, tin[N], tout[N]; ll val[N], bit[N]; vector<int> adj[N]; void dfs(int v, int parent) { tin[v] = timer++; // v's cell in the flat array for (int to : adj[v]) if (to != parent) dfs(to, v); tout[v] = timer; // one past the last node below v } void add(int i, ll x) { // cell i grows by x for (i++; i <= n; i += i & -i) bit[i] += x; // i++: our cells start at 0, bit[] at 1 } ll prefix(int i) { // sum of the first i cells ll s = 0; for (; i > 0; i -= i & -i) s += bit[i]; return s; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> q; for (int v = 1; v <= n; v++) cin >> val[v]; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0); for (int v = 1; v <= n; v++) add(tin[v], val[v]); while (q--) { int type, s; cin >> type >> s; if (type == 1) { ll x; cin >> x; add(tin[s], x - val[s]); // a Fenwick tree adds; it cannot set val[s] = x; } else { cout << prefix(tout[s]) - prefix(tin[s]) << "\n"; } } }
import sys def main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) val = [0] + [int(x) for x in data[2:2 + n]] adj = [[] for _ in range(n + 1)] pos = 2 + n for _ in range(n - 1): a, b = int(data[pos]), int(data[pos + 1]); pos += 2 adj[a].append(b); adj[b].append(a) parent, tin, order, stack = [0] * (n + 1), [0] * (n + 1), [], [1] while stack: # the order of entry is the flat array v = stack.pop(); tin[v] = len(order); order.append(v) for to in adj[v]: if to != parent[v]: parent[to] = v; stack.append(to) size = [1] * (n + 1) for v in reversed(order): # so tout[v] = tin[v] + size[v] size[parent[v]] += size[v] bit = [0] * (n + 1) def add(i, x): # cell i grows by x i += 1 while i <= n: bit[i] += x; i += i & -i def prefix(i): # sum of the first i cells s = 0 while i > 0: s += bit[i]; i -= i & -i return s for v in range(1, n + 1): add(tin[v], val[v]) out = [] for _ in range(q): if data[pos] == b'1': s, x = int(data[pos + 1]), int(data[pos + 2]); pos += 3 add(tin[s], x - val[s]); val[s] = x # add the difference else: s = int(data[pos + 1]); pos += 2 out.append(prefix(tin[s] + size[s]) - prefix(tin[s])) print('\n'.join(map(str, out))) main()
Adding x instead of the difference. Add x − old value. And the block ends one before tout.
Store the ancestor 1, 2, 4, 8 … steps up. Each row comes from the row below. The bits of k say which jumps to take.
k = 13. Which jumps does a k-th ancestor query take?
13 is 1101 in binary, so the jumps are 1, 4 and 8.
How is up[j][v] computed from the row below it?
A jump of 2ʲ is two jumps of 2ʲ⁻¹.
GIVEN · ASKEDparent[] with root 0. Many calls getKthAncestor(node, k): return the node k steps above, or −1 if there is none. k ≤ n.
A class with a constructor and a method getKthAncestor(node, k) that is called many times.
Store the ancestors 1, 2, 4 … steps up; each row comes from the one before. A query follows the set bits of k. −1 means no ancestor.
class TreeAncestor { int LOG; vector<vector<int>> up; // up[j][v]: the ancestor 2^j above v, or -1 public: TreeAncestor(int n, vector<int>& parent) { LOG = 1; while ((1 << LOG) <= n) LOG++; // 1 << LOG is 2^LOG; the statement promises k <= n up.assign(LOG, vector<int>(n, -1)); up[0] = parent; for (int j = 1; j < LOG; j++) for (int v = 0; v < n; v++) if (up[j-1][v] != -1) // the half jump stayed inside the tree up[j][v] = up[j-1][ up[j-1][v] ]; } int getKthAncestor(int node, int k) { for (int j = 0; j < LOG && node != -1; j++) if ((k >> j) & 1) node = up[j][node]; // digit j of k is 1: jump 2^j return node; } };
class TreeAncestor { int LOG; int[][] up; // up[j][v]: the ancestor 2^j above v, or -1 public TreeAncestor(int n, int[] parent) { LOG = 32 - Integer.numberOfLeadingZeros(n); // 2^LOG > n up = new int[LOG][n]; up[0] = parent; for (int j = 1; j < LOG; j++) for (int v = 0; v < n; v++) up[j][v] = up[j-1][v] == -1 ? -1 : up[j-1][ up[j-1][v] ]; } public int getKthAncestor(int node, int k) { for (int j = 0; j < LOG && node != -1; j++) if (((k >> j) & 1) == 1) node = up[j][node]; // digit j of k is 1 return node; } }
class TreeAncestor: def __init__(self, n, parent): self.LOG = n.bit_length() # 2^LOG > n, so every k <= n fits self.up = [parent] # up[j][v]: the ancestor 2^j above v, or -1 for j in range(1, self.LOG): prev = self.up[-1] self.up.append([-1 if prev[v] == -1 else prev[prev[v]] for v in range(n)]) def getKthAncestor(self, node, k): j = 0 while k and node != -1: if k & 1: # bit j of k is set: jump 2^j node = self.up[j][node] k >>= 1; j += 1 return node
Indexing with −1. A jump that leaves the tree stores −1; test it before using it as an index.
Lift the deeper node to the same depth. Then try jumps from largest down, taking one only if the two land on different nodes. They stop one below the LCA.
In the second loop of the LCA, a jump is taken only when up[j][u] != up[j][v]. Why not jump when they are equal?
Landing on the same node means a common ancestor, but maybe far above the lowest one.
depth[a] = 7, depth[b] = 4 and depth[lca(a, b)] = 2. What is the distance from a to b?
a climbs 7 − 2 = 5 edges and the path goes down 4 − 2 = 2 to b: 7 in total.
GIVEN · ASKEDThe boss ei of each employee 2 … n, with ei < i, and q pairs. Print the lowest boss the two share.
“The lowest common boss”, up to 2·10⁵ times. One walk per pair is too slow.
Lift the deeper node to the same depth. If they match, done. Else try jumps largest first, taking only those that land on different nodes. Answer: the parent.
#include <bits/stdc++.h> using namespace std; const int N = 200005, LOG = 18; // 2^18 = 262144 > N int up[LOG][N], depth[N]; // up[j][v]: 2^j bosses above v, 0 = none int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[j][u]; // level the depths if (u == v) return u; // v was above u all along for (int j = LOG - 1; j >= 0; j--) if (up[j][u] != up[j][v]) { // still apart: this jump is safe u = up[j][u]; v = up[j][v]; } return up[0][u]; // one step below the meeting point } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; for (int v = 2; v <= n; v++) { cin >> up[0][v]; // this statement promises e_i <= i - 1 (problem 3 did not), depth[v] = depth[up[0][v]] + 1; // so the boss's depth is already known } for (int j = 1; j < LOG; j++) for (int v = 1; v <= n; v++) up[j][v] = up[j-1][ up[j-1][v] ]; while (q--) { int a, b; cin >> a >> b; cout << lca(a, b) << "\n"; } }
import sys def main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) LOG = max(1, n.bit_length()) up = [[0, 0] + [int(x) for x in data[2:n + 1]]] # up[0] = boss, 0 = none depth = [0] * (n + 1) for v in range(2, n + 1): # this input promises boss < v depth[v] = depth[up[0][v]] + 1 for j in range(1, LOG): prev = up[-1] up.append([prev[prev[v]] for v in range(n + 1)]) out, pos = [], n + 1 for _ in range(q): u, v = int(data[pos]), int(data[pos + 1]); pos += 2 if depth[u] < depth[v]: u, v = v, u diff, j = depth[u] - depth[v], 0 while diff: # level the depths if diff & 1: u = up[j][u] diff >>= 1; j += 1 if u != v: for j in range(LOG - 1, -1, -1): if up[j][u] != up[j][v]: # still apart: this jump is safe u, v = up[j][u], up[j][v] u = up[0][u] # one step below the meeting point out.append(u) print('\n'.join(map(str, out))) main()
Jumps smallest first. Go from the largest down. And keep the u == v check after levelling.
GIVEN · ASKEDA tree as n − 1 edges and q pairs. Print the number of edges between a and b.
“The distance between a and b”, for up to 2·10⁵ pairs.
Distance = depth[a] + depth[b] − 2·depth[lca]. All the work is the LCA (problem 13).
#include <bits/stdc++.h> using namespace std; const int N = 200005, LOG = 18; // 2^18 = 262144 > N int up[LOG][N], depth[N]; // up[j][v]: 2^j steps above v, 0 = none vector<int> adj[N]; void dfs(int v, int parent) { up[0][v] = parent; for (int to : adj[v]) { if (to == parent) continue; depth[to] = depth[v] + 1; dfs(to, v); } } int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int j = 0; j < LOG; j++) if ((diff >> j) & 1) u = up[j][u]; // level the depths if (u == v) return u; // v was above u all along for (int j = LOG - 1; j >= 0; j--) if (up[j][u] != up[j][v]) { // still apart: this jump is safe u = up[j][u]; v = up[j][v]; } return up[0][u]; // one step below the meeting point } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; adj[a].push_back(b); adj[b].push_back(a); } dfs(1, 0); for (int j = 1; j < LOG; j++) for (int v = 1; v <= n; v++) up[j][v] = up[j-1][ up[j-1][v] ]; while (q--) { int a, b; cin >> a >> b; // up to the LCA, then down again cout << depth[a] + depth[b] - 2 * depth[lca(a, b)] << "\n"; } }
import sys def main(): data = sys.stdin.buffer.read().split() n, q = int(data[0]), int(data[1]) adj = [[] for _ in range(n + 1)] pos = 2 for _ in range(n - 1): a, b = int(data[pos]), int(data[pos + 1]); pos += 2 adj[a].append(b); adj[b].append(a) LOG = max(1, n.bit_length()) parent, depth, stack = [0] * (n + 1), [0] * (n + 1), [1] while stack: # depth and parent from one walk v = stack.pop() for to in adj[v]: if to != parent[v]: parent[to] = v; depth[to] = depth[v] + 1; stack.append(to) up = [parent] for j in range(1, LOG): prev = up[-1] up.append([prev[prev[v]] for v in range(n + 1)]) out = [] for _ in range(q): a, b = int(data[pos]), int(data[pos + 1]); pos += 2 u, v = (a, b) if depth[a] >= depth[b] else (b, a) diff, j = depth[u] - depth[v], 0 while diff: # level the depths if diff & 1: u = up[j][u] diff >>= 1; j += 1 if u != v: for j in range(LOG - 1, -1, -1): if up[j][u] != up[j][v]: # still apart: this jump is safe u, v = up[j][u], up[j][v] u = up[0][u] # u is now the LCA out.append(depth[a] + depth[b] - 2 * depth[u]) print('\n'.join(map(str, out))) main()
Subtracting depth[lca] once. It is on both root paths, so subtract it twice.
Moving the root from a node to its child brings sz nodes one closer and pushes n − sz one further. So each new answer costs O(1).
n = 10, ans[v] = 30, and the child c has sz[c] = 3. What is ans[c]?
The 3 nodes on c's side come one step closer; the other 7 go one step further.
Why does the second pass go from the root downward, when the first went from the leaves upward?
Pass 1 needs children finished first. Pass 2 needs parents finished first.
GIVEN · ASKEDA tree on nodes 0 … n − 1. For every node, return the sum of its distances to all the others.
“For every node, the sum of distances to all others.” Each answer depends on the whole tree.
Compute the root's answer once. Moving the root to child c: ans[c] = ans[v] − sz[c] + (n − sz[c]). A second walk fills them all.
// Two passes: collect into root 0, then move the root along every edge. vector<vector<int>> adj; vector<int> sz, sub, ans; int total; void collect(int v, int p) { // pass 1: sizes and sums below v for (int to : adj[v]) { if (to == p) continue; collect(to, v); sz[v] += sz[to]; sub[v] += sub[to] + sz[to]; // each node under `to` is 1 further from v } } void spread(int v, int p) { // pass 2: ans[v] is final here for (int to : adj[v]) { if (to == p) continue; ans[to] = ans[v] - sz[to] + (total - sz[to]); // closer, then further spread(to, v); } } vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) { total = n; adj.assign(n, vector<int>()); sz.assign(n, 1); sub.assign(n, 0); ans.assign(n, 0); for (auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); } collect(0, -1); ans[0] = sub[0]; // below the root is the whole tree spread(0, -1); return ans; }
// Two passes: collect into root 0, then move the root along every edge. List<List<Integer>> adj = new ArrayList<>(); int[] sz, sub, ans; int total; void collect(int v, int p) { // pass 1: sizes and sums below v sz[v] = 1; for (int to : adj.get(v)) { if (to == p) continue; collect(to, v); sz[v] += sz[to]; sub[v] += sub[to] + sz[to]; // each node under `to` is 1 further from v } } void spread(int v, int p) { // pass 2: ans[v] is final here for (int to : adj.get(v)) { if (to == p) continue; ans[to] = ans[v] - sz[to] + (total - sz[to]); // closer, then further spread(to, v); } } public int[] sumOfDistancesInTree(int n, int[][] edges) { total = n; sz = new int[n]; sub = new int[n]; ans = new int[n]; for (int i = 0; i < n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); } collect(0, -1); ans[0] = sub[0]; // below the root is the whole tree spread(0, -1); return ans; }
# Two passes: collect into root 0, then move the root along every edge. def sumOfDistancesInTree(n, edges): adj = [[] for _ in range(n)] for a, b in edges: adj[a].append(b); adj[b].append(a) parent, order, stack = [-1] * n, [], [0] while stack: # parents come out before children v = stack.pop(); order.append(v) for to in adj[v]: if to != parent[v]: parent[to] = v; stack.append(to) sz, sub = [1] * n, [0] * n for v in reversed(order): # pass 1: children before parents p = parent[v] if p != -1: sz[p] += sz[v] sub[p] += sub[v] + sz[v] # each node under v is 1 further from p ans = [0] * n ans[0] = sub[0] # below the root is the whole tree for v in order: # pass 2: parents before children if v != 0: ans[v] = ans[parent[v]] - sz[v] + (n - sz[v]) return ans
Computing ans[c] before ans[v] is final. The second pass goes parent before child.
Nine moves, and each has a phrase in the statement that gives it away.
build adjacency lists, choose a root, walk with the parent as the only guard
ROOT AND WALKO(n)each node returns its own total after adding what its children return
SUBTREE FOLDO(n)keep the two longest arms at every node: score both, return one
DIAMETERO(n)degrees only: remove the leaves in rounds until the middle is left
PEEL THE LEAVESO(n)hand up two numbers, node used and node free, and let the parent choose
TAKE OR SKIPO(n)entry times flatten the tree, and a subtree becomes one array range
ENTRY AND EXIT TIMESO(n) build · O(log n) each with a Fenwick treea table of jumps of 1, 2, 4, 8 …; follow the set bits of k
BINARY LIFTINGO(log n) eachlevel the depths, lift both while they differ; distance = da + db − 2·dlca
LCA BY LIFTINGO(log n) eachsolve one root, then move the root across each edge in O(1)
REROOTINGO(n)A problem gives n − 1 edges and asks, for each of 10⁵ queries, how many nodes are in the subtree of v when the tree is rooted at 1. Which tool answers it?
Fixed root, no changes between queries: one postorder fills every sz[v], and each query is a lookup.
For every node, report the distance to the node farthest from it. Which technique fits?
It depends on the part above the node too, so one postorder is not enough. Rerooting adds the part above in a second pass.
Entry and exit times turn which kind of question into a question about an array range?
A DFS finishes a subtree before leaving, so a subtree's nodes get consecutive positions.
LCA(u, v) is needed for 2·10⁵ pairs on a tree of 2·10⁵ nodes. What does binary lifting cost?
log n rows of n cells. A query levels the depths, then tries each jump size once.
None of these crash. Each one returns an answer that looks reasonable.
An edge list has no direction. Store each edge both ways, or part of the tree can't be reached.
adj[v].size() == 1 means leaf, except at the root, which also has degree 1 with a single child.
if (d > best1) best1 = d forgets the old best. Move best1 into best2 before overwriting it.
Collapsing the pair to max(skip, take) too early. The parent needs to know if the child is free; keep both.
Trying jumps 1, 2, 4 … upward stops short. Run from the largest jump down.
ans[child] comes from ans[parent], so the second pass must visit parents first.
Nine moves on one page. The right column is the cue for each.
Edge lists became rooted trees; values folded up; leaves peeled to the middle; entry times flattened subtrees; jump tables climbed in log n; rerooting moved the root in O(1).
Module 18. Fifteen problems: seven on LeetCode, six on CSES, two on Codeforces.
Not a preference — an arithmetic one. Every slide is a fixed 1280 × 720 stage: a graph animating beside the code that drives it, with the problems laid out two columns wide. It scales as a single piece, so on a screen this size the body text comes out around 4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean losing the thing that makes it worth reading.