Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Bob makes directed guesses of the form 'u is the parent of v'. Alice picks the root uniformly at random over all n nodes, and Bob wins if at least k guesses turn out correct. The answer is (number of roots that make ≥ k guesses correct) / n, reduced. Compute the correct count for root = 1 with one DFS, then reroot in O(1) per edge: moving the root across edge (u, v) only flips the two guesses on that edge. Count winning roots and reduce the fraction. O(n + g).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize an 'answer for every root' tree problem as a rerooting (re-rooting DP) candidate instead of brute-forcing n separate DFS runs, and whether you correctly treat each guess as a directed parent→child pair.
Where candidates slip
Treating guesses as undirected edges, recomputing from scratch at each root (O(n²)), or botching the reroot delta — forgetting that crossing edge (u, v) both removes guess (u, v) and adds guess (v, u).
How to stand out
Derive the O(1) reroot update from first principles ('only edge (u,v)'s two guesses flip'), note the answer is wins/n reduced by gcd, and mention that gcd(0, n) already yields 0/1.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewNeed an answer for every root?One fixed root only?YesNoExplore the full treeCollapse the tree
How to read it:Solid edges are the tree; dashed arrows are Bob's directed guesses 'parent → child'. Rooting at 1 makes both guesses correct.
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Re-root From Every Node
1Hint 1Explore hintHide hint
The probability is (winning roots) / n. What is the most direct way to know whether a specific root is a winner?
2Hint 2Explore hintHide hint
Fix a root, run a DFS/BFS that records each node's parent, then count how many guesses (u, v) satisfy 'parent of v == u'. Repeat for all n roots.
3Hint 3Explore hintHide hint
Each root costs O(n + g); doing it n times is O(n·(n + g)) — correct but quadratic. Use it to validate the fast solution on small inputs.
A · Core idea
The definition of the answer is operational, so the brute force just executes the definition.
The loop. For every candidate root r from 1 to n: traverse the tree from r, assigning each visited node its parent in that rooting. Then scan all g guesses; a guess (u, v) is correct iff the parent recorded for v equals u. If the number of correct guesses is ≥ k, increment wins.
Why it is correct. It computes, for each root, exactly the quantity the problem defines — the count of correct guesses — and compares it to k. Nothing is approximated. This makes it the ideal oracle to diff against the optimized version on random small trees.
Why we don't ship it. Re-traversing the whole tree from scratch for each of the n roots throws away an enormous amount of shared structure: most parent relationships are identical between adjacent roots. That redundancy is exactly what the rerooting solution exploits. At n = 10⁵, O(n²) is hopeless; mention this approach, then improve it.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2],[1,3],[3,4]], guesses = [[1,2],[3,4]], k = 2Array state
root 1
(1,2)✓ (3,4)✓
wins = 2, n = 4 → 2/4 = 1/2C · Code with teaching comments
Reference implementation previewpublic String storyOfATree(int n, int[][] edges, int[][] guesses, int k) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]);Explore the full codeHide the full code
D · Why it works and complexityO(n · (n + g)) timeO(n + g) spaceOpen the invariant and proofExplore the proofHide the proof
Brute force here is the specification made executable. Its weakness — recomputing nearly-identical parent maps n times — points directly at the optimization: when the root moves to a neighbor, almost nothing changes.
ComplexityO(n · (n + g)) time, O(n + g) space — Each root requires a full traversal O(n) plus checking g guesses O(g). Running that for all n possible roots gives O(n · (n + g)). With n up to 10⁵ this is ~10¹⁰ operations — far too slow, but conceptually simple and a perfect correctness oracle.
E · Edge cases and pitfalls3Treating a guess as undirected — (u, v) and (v, u) are different claims.Explore edge casesHide edge cases
Pitfalls
- Treating a guess as undirected — (u, v) and (v, u) are different claims.
- Re-allocating visited[] and recomputing for all n roots — accepted only as an oracle, never as the final answer at n = 10⁵.
- Forgetting to reduce the fraction with gcd.
Approach 2 of 2 · Optimal
Rerooting DP (Optimal)
1Hint 1Explore hintHide hint
Brute force recomputes almost the same parent map for every root. When the root moves from u to an adjacent v, which guesses can possibly change their correctness?
2Hint 2Explore hintHide hint
Only the guesses on the edge (u, v). Guess (u, v) ('u parent of v') was correct while rooted on u's side and is wrong once v is the root's side; guess (v, u) flips the other way.
3Hint 3Explore hintHide hint
Compute correct[1] with one DFS. Then BFS/DFS outward: correct[child] = correct[parent] − [ (parent,child) guessed ] + [ (child,parent) guessed ]. Count nodes with correct ≥ k.
A · Core idea
The brute force is wasteful because adjacent roots share nearly all parent relationships. Rerooting computes the answer once and then transports it across the tree.
Step 1 — anchor at root 1. One DFS from node 1 records each node's parent and counts base: the number of guesses (u, v) where u is the parent of v in this rooting. Set correct[1] = base.
Step 2 — the reroot delta. Consider an edge between u (already settled, root on its side) and its child v. Imagine physically moving the root from u's side to v's side. Every guess except those on this edge keeps the same parent→child orientation, so its correctness is unchanged. Only two guesses can flip:
(u, v)— 'u is parent of v' — was correct (root on u's side) and becomes wrong → subtract 1 if it was guessed.(v, u)— 'v is parent of u' — was wrong and becomes correct → add 1 if it was guessed.
So correct[v] = correct[u] − [(u,v) guessed] + [(v,u) guessed].
Why only that edge changes. Re-rooting from u to v reverses the direction of exactly one edge in the rooted tree — the u–v edge. Every other edge keeps the same parent and child, so every other guess's truth value is untouched. That locality is the entire reason the update is O(1).
Step 3 — propagate and tally. Process nodes in preorder (parent before child) so each correct[u] is final before its children read it. After filling correct[] for all n nodes, count how many satisfy correct[node] ≥ k; that is wins. Return wins / n reduced by gcd (and gcd(0, n) = n already gives 0/1).
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2],[1,3],[3,4]], guesses = [[1,2],[3,4]], k = 2Array state
DFS root 1
base = 2
2/4 → gcd 2 → 1/2C · Code with teaching comments
D · Why it works and complexityO(n + g) timeO(n + g) spaceOpen the invariant and proofExplore the proofHide the proof
Re-rooting reverses exactly one edge's parent/child relationship per move, so any quantity that decomposes over edges updates in O(1). Here each edge carries at most two directed guesses, making the delta a clean ±1. This 'compute once, slide everywhere' template recurs in 'Sum of Distances in Tree' and many tree-DP problems.
ComplexityO(n + g) time, O(n + g) space — Building the adjacency list and guess set is O(n + g). The first DFS is O(n). The reroot pass visits each node once and does O(1) work per edge → O(n). Counting winners is O(n). Total O(n + g), with O(n + g) space for the adjacency list, guess set, and per-node arrays.
E · Edge cases and pitfalls7g = 0 (no guesses) — correct[node] = 0 for all roots; if k ≥ 1 then wins = 0 → 0/1. If k = 0 every root wins → 1/1 (but k ≥ 1 per constraints).Explore edge casesHide edge cases
Edge cases handled
g = 0 (no guesses)correct[node] = 0 for all roots; if k ≥ 1 then wins = 0 → 0/1. If k = 0 every root wins → 1/1 (but k ≥ 1 per constraints).Both (u,v) and (v,u) guessed on one edgeCrossing the edge does −1 and +1 simultaneously — net 0 — which is correct, since exactly one of the two is always right.n = 1Single node, no edges, no guesses; wins = (k ≤ 0 ? 1 : 0). With k ≥ 1, answer is 0/1.
Pitfalls
- Processing children before parents — use preorder so correct[parent] is final first.
- Forgetting the +1 for the reverse guess (v, u) when crossing an edge.
- Encoding guesses as unordered edges, collapsing (u, v) and (v, u).
- Recursive DFS at n = 10⁵ risking stack overflow — use an explicit stack.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String storyOfATree(int n, int[][] edges, int[][] guesses, int k) { List<List<Integer>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) { adj.get(e[0]).add(e[1]);Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Undirected guess
A guess (u, v) asserts u is the parent of v. Storing it as an unordered edge makes (v, u) look guessed too, double-counting correctness and corrupting the reroot delta.
Explore the code comparisonHide the code comparison
Undirected guess
A guess (u, v) asserts u is the parent of v. Storing it as an unordered edge makes (v, u) look guessed too, double-counting correctness and corrupting the reroot delta.
Don't write this
guessed = set()
for a, b in guesses:
guessed.add(frozenset((a, b))) # loses directionWrite this instead
guessed = {(a, b) for a, b in guesses} # ordered: a is parent of b2Incomplete reroot delta
Crossing edge (u, v) flips two guesses: (u, v) goes right→wrong and (v, u) goes wrong→right. Applying only the −1 undercounts every root on v's side.
Explore the code comparisonHide the code comparison
Incomplete reroot delta
Crossing edge (u, v) flips two guesses: (u, v) goes right→wrong and (v, u) goes wrong→right. Applying only the −1 undercounts every root on v's side.
Don't write this
int c = correct[u];
if (guessed.contains(key(u, v))) c--; // forgot the reverse
correct[v] = c;Write this instead
int c = correct[u];
if (guessed.contains(key(u, v))) c--;
if (guessed.contains(key(v, u))) c++;
correct[v] = c;3Recomputing per root
Re-running a DFS from each of n roots is O(n²). At n = 10⁵ it times out; rerooting reuses the root-1 computation and slides it in O(1) per edge.
Explore the code comparisonHide the code comparison
Recomputing per root
Re-running a DFS from each of n roots is O(n²). At n = 10⁵ it times out; rerooting reuses the root-1 computation and slides it in O(1) per edge.
Don't write this
for root in range(1, n + 1):
# full DFS + recount guesses from scratch -> O(n^2)
...Write this instead
# one DFS for correct[1], then
for u in order:
for v in children(u):
correct[v] = correct[u] - guessed(u, v) + guessed(v, u)Revise
Carry the pattern into the interview
Pattern to remember
Reroot DP — compute once at root 1, slide the root edge by edge
Code pattern to memorize
guessed = set of directed pairs (a, b) meaning 'a is parent of b'
DFS from root 1:
base += 1 for every tree edge parent u → child v with (u, v) in guessed
correct[1] = base
reroot (preorder, parent before child):
for child v of u:
correct[v] = correct[u]
if (u, v) in guessed: correct[v] -= 1 # u was parent, no longer
if (v, u) in guessed: correct[v] += 1 # v becomes parent of u
wins = count of nodes with correct >= k
answer = wins / n reduced by gcdRules to remember
- 1A guess (u, v) means u is the parent of v — it is directed, so store it as an ordered pair, not an unordered edge.
- 2Only the two guesses living on edge (u, v) change when the root crosses that edge — every other guess is unaffected. That O(1) update is the whole trick.
- 3Compute
correct[1]with one DFS, then propagate to every node in preorder so each parent's value is ready before its children. - 4The probability denominator is always n (every node is an equally likely root); reduce
wins/nwithgcd. - 5When
wins = 0,gcd(0, n) = n, so the reduced fraction is0/1— no special case needed.
Use this pattern when
- An answer is needed for **every possible root** of a tree, not just one fixed root
- Re-running an O(n) DFS from each of n roots would be O(n²) and too slow
- The quantity at a child differs from its parent's by an **O(1) local correction**
- Tree / forest structure where moving the root flips only edge-local state
Choose another pattern when
- A single fixed root → one plain DFS, no rerooting
- General graph with cycles → rerooting's 'one edge flips' invariant breaks
- The per-node answer can't be derived from its parent in O(1) → rerooting gives no speedup
- You actually need each root's full subtree recomputed → no shortcut, accept O(n²) or rethink
Interview takeaway
Rerooting turns 'answer this for all n roots' from O(n²) into O(n): solve once at an arbitrary root, then realize that sliding the root over one edge changes only the handful of facts attached to that edge. Here exactly two directed guesses live on each edge, so each move is a ±1 fix.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Rerooting (Re-rooting DP). Recognize it whenever a tree problem asks for an answer at every node/root and the child's answer differs from the parent's by an O(1), edge-local correction. Solve once at an arbitrary root, then propagate. Here each edge holds at most two directed guesses, so the delta is a clean ±1.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Sum of Distances in TreeComing soonClassic rerooting: compute distances from one root, then slide — answer[child] = answer[parent] − subtreeSize[child] + (n − subtreeSize[child]).
- Tree Distances / Maximum Depth From Every NodeComing soonTwo DFS passes (down then up) propagate the farthest distance to every node — the same compute-once-then-reroot idea.
- Count Subtrees / Rerooting AggregatesComing soonAny edge-decomposable aggregate (sums, counts, max) can be rerooted in O(n) once the O(1) parent→child delta is known.