INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING
01
00/15
01 / COVER MODULE 18 · GENERAL TREES
INVARIANT · MODULE 18 · GENERAL TREES
NO LEFT, NO RIGHT

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.

15Problems
6Families
9Units
9Live walks
← → ↑ ↓  or  W A S D  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
02 / INDEX PRESS I FROM ANYWHERE

INDEX — ALL 15 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.

ROOT AND WALK · 02
FOLD UP FROM THE CHILDREN · 04
PEEL THE LEAVES · 02
TWO NUMBERS PER NODE · 02
PREPROCESS, THEN QUERY · 04
EVERY ROOT AT ONCE · 01
SOLVED HAS A JUDGE LINK
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
03 / MECHANISM UNIT 01 · EDGE LIST TO ROOTED TREE

THE INPUT IS A LIST OF EDGES, NOT A TREE

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
04 / DRILL UNIT 01 · Edge List to Rooted Tree

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · BUG

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
05 / PROBLEM #01 · ROOTING · MED

Time Needed to Inform All Employees

MED rooting ▶ SOLVE ON LEETCODE

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.

SIGNAL — WHAT GIVES IT AWAY

“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.

INTUITION

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.

STEPS
  1. kids[m] = every v with manager[v] == m
  2. dfs(v) returns the minutes until everyone under v knows
  3. dfs(v) = informTime[v] + the largest dfs(child)
  4. A leaf has no children, so it returns its informTime, which the statement promises is 0
  5. The answer is dfs(headID)
BRUTEO(n²) walking up from each employee
→
OPTIMALO(n)
↕ SCROLL
// 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);
}
TIMEO(n)each employee is visited once
SPACEO(n)children lists and the recursion
TRAP

Adding children's times. Branches run at the same time: take the largest, not the sum.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
06 / PROBLEM #02 · ROOTING · MED

Kefa and Park

MED rooting ▶ SOLVE ON CODEFORCESCodeforces 580C, rated 1500.

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.

SIGNAL — WHAT GIVES IT AWAY

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.

INTUITION

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.

STEPS
  1. Build adjacency lists from the n − 1 edges
  2. dfs(v, parent, streak): streak arrives as the run of cats ending at v's parent
  3. First line makes it the run ending at v: streak = cat[v] ? streak + 1 : 0; if streak > m, return
  4. Recurse into every neighbour except parent
  5. No neighbour except parent means v is a leaf, so count it
BRUTEO(n²) re-walking each root-to-leaf path
→
OPTIMALO(n)
↕ SCROLL
#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";
}
TIMEO(n)every vertex is entered at most once
SPACEO(n)adjacency lists and the recursion
TRAP

Leaf test adj[v].size() == 1. The root also has one neighbour with a single child.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
07 / MECHANISM UNIT 02 · SUBTREE SIZES

EVERY NODE RETURNS ONE NUMBER ABOUT ITS SUBTREE

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
08 / DRILL UNIT 02 · Subtree Sizes · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
09 / PROBLEM #03 · FOLD · EASY

Subordinates

EASY fold ▶ SOLVE ON CSESCSES does not rate its problems, so the chip is this deck's estimate. Submit the Python tab as PyPy3.

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.

SIGNAL — WHAT GIVES IT AWAY

“For each employee, count the subordinates.” An answer for every node, where each answer covers the node's whole subtree.

INTUITION

Size = 1 + the children's sizes, in one postorder. Subordinates = size − 1.

STEPS
  1. kids[boss] gets v, for v = 2 … n
  2. dfs(v) starts with sz[v] = 1
  3. For each child c, call dfs(c), then sz[v] += sz[c]
  4. Print sz[v] − 1 for v = 1 … n
BRUTEO(n²) counting each subtree separately
→
OPTIMALO(n)
↕ SCROLL
#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";
}
TIMEO(n)one postorder pass
SPACEO(n)children lists and the sz array
TRAP

A separate walk per employee. On a chain that is 2·10¹⁰ steps.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
10 / PROBLEM #04 · FOLD · MED

Minimum Time to Collect All Apples in a Tree

MED fold ▶ SOLVE ON LEETCODE

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.

SIGNAL — WHAT GIVES IT AWAY

“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.

INTUITION

An edge is worth walking only if an apple lies below it. The parent adds 2 for each child whose subtree holds an apple.

STEPS
  1. Build adjacency lists; the edges are undirected
  2. dfs(v, parent) returns the seconds spent inside v's subtree
  3. For each child, below = dfs(child, v)
  4. If below > 0 or the child has an apple, cost += below + 2
  5. The answer is dfs(0, −1). Nodes start at 0 here, so the fake parent is −1
BRUTEO(n²) walking up from every apple
→
OPTIMALO(n)
↕ SCROLL
// 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);
}
TIMEO(n)one postorder pass
SPACEO(n)adjacency lists and the recursion
TRAP

Trusting the order inside an edge. [a, b] does not say a is the parent. Add both directions.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
11 / DRILL UNIT 02 · Subtree Sizes · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRANSFER

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
12 / MECHANISM UNIT 03 · DIAMETER OF A GENERAL TREE

ANY NUMBER OF ARMS, BUT A PATH USES TWO

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
13 / DRILL UNIT 03 · Diameter of a General Tree

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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.

DRILL 02 · RECALL

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
14 / PROBLEM #05 · FOLD · MED

Tree Diameter

MED fold ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate. LeetCode 1245 is the same task but is paid.

GIVEN · ASKEDA tree as n − 1 edges. Print the most edges on a path between two nodes.

SIGNAL — WHAT GIVES IT AWAY

“The maximum distance between two nodes.” The longest path in a tree, with no root given and any number of children per node.

INTUITION

Root it anywhere. Every path turns at its highest node and goes down two arms into two different children.

STEPS
  1. Root the tree anywhere, say at node 1
  2. dfs(v, parent) returns the longest arm below v, in edges
  3. For each child, d = dfs(child) + 1; keep the two largest as best1, best2
  4. diameter = max(diameter, best1 + best2)
  5. Return best1
BRUTEO(n²) BFS from every node
→
OPTIMALO(n)
↕ SCROLL
#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";
}
TIMEO(n)one DFS, O(1) work per edge
SPACEO(n)adjacency lists and the recursion
TRAP

Keeping only the longest arm. The second longest is thrown away and the answer comes out short.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
15 / PROBLEM #06 · FOLD · HARD

Longest Path With Different Adjacent Characters

HARD fold ▶ SOLVE ON LEETCODE

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.

SIGNAL — WHAT GIVES IT AWAY

“The longest path such that no pair of adjacent nodes has the same character.” A diameter, with a rule about which arms may join.

INTUITION

Problem 5 with one filter: a child's chain extends through its parent only if their letters differ. Count in nodes.

STEPS
  1. kids[parent[v]] gets v; the root is node 0
  2. dfs(v) returns the longest valid chain going down from v, in nodes
  3. For each child c, len = dfs(c); if s[c] == s[v], do not use it
  4. Keep the two largest len as best1, best2
  5. best = max(best, best1 + best2 + 1); return best1 + 1
BRUTEO(n²) starting a search at every node
→
OPTIMALO(n)
↕ SCROLL
// 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;
}
TIMEO(n)one DFS, O(1) work per edge
SPACEO(n)children lists and the recursion
TRAP

Skipping the call when letters match. Always recurse; only the use of the result is filtered.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
16 / MECHANISM UNIT 04 · PEEL THE LEAVES

NO ROOT AND NO RECURSION, ONLY DEGREES

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
17 / DRILL UNIT 04 · Peel the Leaves

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · TRACE

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
18 / PROBLEM #07 · PEEL · MED

Minimum Height Trees

MED peel ▶ SOLVE ON LEETCODE

GIVEN · ASKEDA tree on nodes 0 … n − 1. Return every node that gives the smallest height when used as the root.

SIGNAL — WHAT GIVES IT AWAY

“Choose the root that gives the smallest height.” The tree is unrooted and the question is about its middle.

INTUITION

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.

STEPS
  1. If n == 1, the answer is [0]
  2. deg[v] = number of neighbours; leaves = every v with deg 1
  3. While more than 2 nodes are left, remove the current leaves together
  4. A removed leaf lowers its neighbour's degree; a neighbour that reaches 1 joins the next round
  5. The last set of leaves is the answer
BRUTEO(n²) BFS from every root
→
OPTIMALO(n)
↕ SCROLL
// 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;
}
TIMEO(n)every node and edge is handled once
SPACEO(n)adjacency lists and degrees
TRAP

Stopping mid-round. Finish each round before checking the count, and handle n = 1 first.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
19 / PROBLEM #08 · PEEL · HARD

Collect Coins in a Tree

HARD peel ▶ SOLVE ON LEETCODE

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.

SIGNAL — WHAT GIVES IT AWAY

“Collect all coins within distance 2”, then return. You choose the start.

INTUITION

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.

STEPS
  1. Build adjacency lists and degrees
  2. Queue every leaf with no coin; removing one may turn its neighbour into another
  3. Twice, remove all current leaves together, coin or not
  4. kept = edges whose two ends are both still present
  5. The answer is 2 × kept
  6. Path 0-1-2-3-4-5-6, coins on 0 and 6: remove 0 and 6, then 1 and 5. Left: 2-3-4, two edges, answer 4.
BRUTEtry every start, walk for the coins
→
OPTIMALO(n)
↕ SCROLL
// 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;
}
TIMEO(n)each vertex is removed at most once
SPACEO(n)adjacency lists, degrees, a queue
TRAP

Mixing the two phases. Trimming runs until no coinless leaf is left; then exactly two rounds remove every leaf.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
20 / MECHANISM UNIT 05 · TAKE OR SKIP

WHEN ONE NUMBER IS NOT ENOUGH, HAND UP TWO

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
21 / DRILL UNIT 05 · Take or Skip

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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.

DRILL 02 · RECALL

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
22 / PROBLEM #09 · TREE DP · MED

Tree Matching

MED tree dp ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate.House Robber III and Binary Tree Cameras in Binary Trees deck 3 are the same take-or-skip idea on a binary tree.

GIVEN · ASKEDA tree as n − 1 edges. Print the most edges you can choose so that no node is on two of them.

SIGNAL — WHAT GIVES IT AWAY

“The most edges with no node used twice.” Choosing an edge blocks its neighbours, like House Robber.

INTUITION

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.

STEPS
  1. skip[v] = Σ max(skip[c], take[c]) over the children
  2. For each child c, rest = skip[v] − max(skip[c], take[c])
  3. take[v] = the largest rest + skip[c] + 1
  4. A leaf has skip = take = 0
  5. The answer is max(skip[root], take[root])
BRUTEO(2ⁿ) trying every set of edges
→
OPTIMALO(n)
↕ SCROLL
#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";
}
TIMEO(n)two loops over each node's children
SPACEO(n)adjacency lists and two arrays
TRAP

Recomputing the other children's sum for each c. On a star that is quadratic.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
23 / PROBLEM #10 · TREE DP · MED

Parsa's Humongous Tree

MED tree dp ▶ SOLVE ON CODEFORCESCodeforces 1528A, rated 1600.

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.

SIGNAL — WHAT GIVES IT AWAY

A choice at every node that affects only its neighbours, and a score summed over the edges.

INTUITION

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.

STEPS
  1. dpLo[v] is the best total inside v's subtree when a_v = l_v, and dpHi[v] when a_v = r_v
  2. For each child c, dpLo[v] += max(dpLo[c] + |l_v − l_c|, dpHi[c] + |l_v − r_c|)
  3. dpHi[v] is the same with r_v in place of l_v
  4. A leaf has both equal to 0
  5. The answer per test is max(dpLo[1], dpHi[1])
BRUTEexponential: every value at every vertex
→
OPTIMALO(n)
↕ SCROLL
#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";
    }
}
TIMEO(n)four comparisons per edge
SPACEO(n)adjacency lists and two arrays
TRAP

Using int. The total overflows 32 bits.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
24 / MECHANISM UNIT 06 · ENTRY AND EXIT TIMES

STAMP THE CLOCK ON THE WAY IN AND ON THE WAY OUT

A DFS finishes a subtree before leaving it, so in entry order each subtree is one unbroken block, from tin to just before tout.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
25 / DRILL UNIT 06 · Entry and Exit Times

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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.

DRILL 02 · RECALL

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).

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
26 / TOOL UNIT 06 · THE FENWICK TREE

A FENWICK TREE IN ONE SCREEN

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.

i12345678
i & -i12141218
bit[1] · 1
bit[2] · 1–2
bit[3] · 3
bit[4] · 1–4
bit[5] · 5
bit[6] · 5–6
bit[7] · 7
bit[8] · 1–8
1
2
3
4
5
6
7
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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
27 / PROBLEM #11 · QUERIES · MED

Subtree Queries

MED queries ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate.

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.

SIGNAL — WHAT GIVES IT AWAY

Updates mixed with subtree sums, so the sums can't be computed once.

INTUITION

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).

STEPS
  1. A DFS from node 1 sets tin[v] = timer++ on entry and tout[v] = timer on exit
  2. Fenwick tree over the positions; add val[v] at cell tin[v]
  3. To update s to x, add (x − val[s]) at cell tin[s], then set val[s] = x
  4. A query on s is prefix(tout[s]) − prefix(tin[s])
BRUTEO(n) per query, walking the subtree
→
OPTIMALO((n + q) log n)
↕ SCROLL
#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";
        }
    }
}
TIMEO((n + q) log n)one DFS, then log n per operation
SPACEO(n)tin, tout and the Fenwick array
TRAP

Adding x instead of the difference. Add x − old value. And the block ends one before tout.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
28 / MECHANISM UNIT 07 · BINARY LIFTING

JUMPS OF 1, 2, 4, 8 … STORED FOR EVERY NODE

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
29 / DRILL UNIT 07 · Binary Lifting

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

k = 13. Which jumps does a k-th ancestor query take?

13 is 1101 in binary, so the jumps are 1, 4 and 8.

DRILL 02 · RECALL

How is up[j][v] computed from the row below it?

A jump of 2ʲ is two jumps of 2ʲ⁻¹.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
30 / PROBLEM #12 · QUERIES · HARD

Kth Ancestor of a Tree Node

HARD queries ▶ SOLVE ON LEETCODE▶ SAME TASK ON CSESCSES 1687, Company Queries I, asks the same question with employees numbered from 1.

GIVEN · ASKEDparent[] with root 0. Many calls getKthAncestor(node, k): return the node k steps above, or −1 if there is none. k ≤ n.

SIGNAL — WHAT GIVES IT AWAY

A class with a constructor and a method getKthAncestor(node, k) that is called many times.

INTUITION

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.

STEPS
  1. LOG = the number of bits needed to write n
  2. up[0][v] = parent[v]
  3. up[j][v] = up[j−1][ up[j−1][v] ], or −1 if the half jump already left the tree
  4. In a query, for each set bit j of k, node = up[j][node]
  5. Stop early if node becomes −1, and return it
BRUTEO(k) per query
→
OPTIMALO(n log n) build · O(log n) query
↕ SCROLL
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;
    }
};
TIMEO(n log n) build · O(log n) querylog n rows of n cells; one jump per set bit
SPACEO(n log n)the jump table
TRAP

Indexing with −1. A jump that leaves the tree stores −1; test it before using it as an index.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
31 / MECHANISM UNIT 08 · LCA AND DISTANCES

LEVEL THE TWO NODES, THEN LIFT THEM TOGETHER

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.

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
32 / DRILL UNIT 08 · LCA and Distances

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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.

DRILL 02 · TRACE

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
33 / PROBLEM #13 · QUERIES · MED

Company Queries II

MED queries ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate.

GIVEN · ASKEDThe boss ei of each employee 2 … n, with ei < i, and q pairs. Print the lowest boss the two share.

SIGNAL — WHAT GIVES IT AWAY

“The lowest common boss”, up to 2·10⁵ times. One walk per pair is too slow.

INTUITION

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.

STEPS
  1. depth[v] = depth[boss[v]] + 1; up[0][v] = boss[v], with 0 above the root
  2. Fill up[j][v] = up[j−1][ up[j−1][v] ]
  3. In lca(u, v), lift the deeper node by the depth difference
  4. If u == v, return u
  5. For j from high to low, lift both if up[j][u] != up[j][v]
  6. Return up[0][u]
BRUTEO(n) per query, climbing both nodes
→
OPTIMALO((n + q) log n)
↕ SCROLL
#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";
    }
}
TIMEO((n + q) log n)log n rows to build; two short loops per query
SPACEO(n log n)the jump table
TRAP

Jumps smallest first. Go from the largest down. And keep the u == v check after levelling.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
34 / PROBLEM #14 · QUERIES · MED

Distance Queries

MED queries ▶ SOLVE ON CSESCSES does not rate its problems; the chip is this deck's estimate.

GIVEN · ASKEDA tree as n − 1 edges and q pairs. Print the number of edges between a and b.

SIGNAL — WHAT GIVES IT AWAY

“The distance between a and b”, for up to 2·10⁵ pairs.

INTUITION

Distance = depth[a] + depth[b] − 2·depth[lca]. All the work is the LCA (problem 13).

STEPS
  1. Root at node 1; one DFS sets depth[v] and up[0][v]
  2. Fill the jump table
  3. For each query, c = lca(a, b)
  4. Print depth[a] + depth[b] − 2 × depth[c]
BRUTEO(n) per query, a BFS from a
→
OPTIMALO((n + q) log n)
↕ SCROLL
#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";
    }
}
TIMEO((n + q) log n)one DFS, log n rows, two short loops per query
SPACEO(n log n)adjacency lists and the jump table
TRAP

Subtracting depth[lca] once. It is on both root paths, so subtract it twice.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
35 / MECHANISM UNIT 09 · REROOTING

SOLVE ONE ROOT, THEN MOVE THE ROOT ALONG AN EDGE

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).

THE TREE
CALL STACK
RESULT
CODE MIRROR
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
36 / DRILL UNIT 09 · Rerooting

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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.

DRILL 02 · RECALL

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
37 / PROBLEM #15 · REROOT · HARD

Sum of Distances in Tree

HARD reroot ▶ SOLVE ON LEETCODE▶ SAME TASK ON CSESCSES 1133, Tree Distances II, is the same task with nodes numbered from 1.

GIVEN · ASKEDA tree on nodes 0 … n − 1. For every node, return the sum of its distances to all the others.

SIGNAL — WHAT GIVES IT AWAY

“For every node, the sum of distances to all others.” Each answer depends on the whole tree.

INTUITION

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.

STEPS
  1. Pass 1, children first, fills sz[v] and sub[v], the sum of distances from v to the nodes below it
  2. sub[v] += sub[c] + sz[c] for each child c
  3. ans[root] = sub[root]
  4. Pass 2, parents first, sets ans[c] = ans[v] − sz[c] + (n − sz[c])
  5. Return ans
BRUTEO(n²) BFS from every node
→
OPTIMALO(n)
↕ SCROLL
// 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;
}
TIMEO(n)two DFS passes
SPACEO(n)adjacency lists and three arrays
TRAP

Computing ans[c] before ans[v] is final. The second pass goes parent before child.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
38 / SIGNALS WHEN YOU SEE X, REACH FOR Y

WHICH MOVE, AND WHAT GIVES IT AWAY

Nine moves, and each has a phrase in the statement that gives it away.

“n − 1 EDGES” / “A PARENT ARRAY”

build adjacency lists, choose a root, walk with the parent as the only guard

ROOT AND WALKO(n)
“FOR EACH NODE, COUNT OR SUM ITS SUBTREE”

each node returns its own total after adding what its children return

SUBTREE FOLDO(n)
“LONGEST PATH” / “MAXIMUM DISTANCE”

keep the two longest arms at every node: score both, return one

DIAMETERO(n)
“BEST ROOT” / OUTER PARTS THAT NEVER MATTER

degrees only: remove the leaves in rounds until the middle is left

PEEL THE LEAVESO(n)
“NO TWO CHOSEN MAY TOUCH” / “MATCHING”

hand up two numbers, node used and node free, and let the parent choose

TAKE OR SKIPO(n)
“UPDATE A NODE, SUM A SUBTREE”

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 tree
“K-TH ANCESTOR”, MANY QUERIES

a table of jumps of 1, 2, 4, 8 …; follow the set bits of k

BINARY LIFTINGO(log n) each
“LOWEST COMMON” / “DISTANCE BETWEEN”

level the depths, lift both while they differ; distance = da + db − 2·dlca

LCA BY LIFTINGO(log n) each
“FOR EVERY NODE AS THE ROOT”

solve one root, then move the root across each edge in O(1)

REROOTINGO(n)
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
39 / RECALL RETRIEVAL, NOT RECOGNITION · 1 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · TRANSFER

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.

DRILL 02 · TRANSFER

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
40 / RECALL RETRIEVAL, NOT RECOGNITION · 2 OF 2

NAME THE MOVE FROM THE STATEMENT

DRILL 01 · RECALL

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.

DRILL 02 · RECALL

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.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
41 / TRAPS PLAUSIBLE, WRONG, AND SILENT

SIX WAYS TO BE PLAUSIBLY WRONG

None of these crash. Each one returns an answer that looks reasonable.

READING [a, b] AS PARENT THEN CHILD

An edge list has no direction. Store each edge both ways, or part of the tree can't be reached.

LEAF MEANS DEGREE 1

adj[v].size() == 1 means leaf, except at the root, which also has degree 1 with a single child.

ONE BEST ARM INSTEAD OF TWO

if (d > best1) best1 = d forgets the old best. Move best1 into best2 before overwriting it.

ONE NUMBER WHERE THE PARENT NEEDS TWO

Collapsing the pair to max(skip, take) too early. The parent needs to know if the child is free; keep both.

THE LCA LOOP FROM SMALL JUMPS TO LARGE

Trying jumps 1, 2, 4 … upward stops short. Run from the largest jump down.

REROOTING IN THE WRONG ORDER

ans[child] comes from ans[parent], so the second pass must visit parents first.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
42 / CHEATSHEET REVISION SURFACE

ONE SCREEN, THE WHOLE DECK

Nine moves on one page. The right column is the cue for each.

ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Root an edge list
O(n)
O(n)
n − 1 undirected edges; dfs(v, parent), skip the parent
Subtree sizes
O(n)
O(n)
an answer per node about everything below it
Diameter, any degree
O(n)
O(n)
longest path; two longest arms at every node
Peel the leaves
O(n)
O(n)
the middle of an unrooted tree; layers never visited
Take or skip
O(n)
O(n)
choosing a node or an edge blocks its neighbours
Entry and exit times
O(n) + O(log n) with Fenwick
O(n)
subtree = array range; ancestor test in O(1)
Binary lifting
O(n log n) + O(log n)
O(n log n)
k-th ancestor, many queries, fixed tree
LCA by lifting
O(n log n) + O(log n)
O(n log n)
lowest common ancestor; da + db − 2·dlca
Rerooting
O(n)
O(n)
the same answer for every possible root
INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
43 / CLOSE MODULE 18 · GENERAL TREES

ROOT IT YOURSELF

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).

00%
OF THIS DECK SOLVED
← ALL TOPICS← BINARY TREES 3← BST

Module 18. Fifteen problems: seven on LeetCode, six on CSES, two on Codeforces.

INVARIANT · GENERAL TREES · ROOTING, TREE DP, LIFTING & REROOTING · GENERAL TREES
■ TOO SMALL TO READ
1280×720
INVARIANT · MODULE 18 · GENERAL TREES

This one needs a laptop

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.

YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
WATCH IT RUN, THEN RUN IT FROM MEMORY
Your progress is saved per device, so anything you tick on the laptop will be waiting there.