Trees are the simplest non-trivial graphs — they have no cycles, which means many problems that are NP-hard on general graphs become solvable on trees. Game theory on trees is particularly rich because:
Unique paths: Between any two nodes, there's exactly one path — distance is well-defined and easy to compute.
Leaves are special: The leaves (degree-1 nodes) are natural "endpoints" that get removed in many games.
Centroid decomposition: Trees have centroids — nodes whose removal splits the tree into balanced subtrees.
Parity arguments: Many tree games reduce to counting nodes modulo 2, or comparing distances.
Permutations as graphs: Permutation games often reduce to analyzing cycles and inversions.
In this article, we'll cover three classic problem families: leaf-removal games on trees, pursuit-evasion (tag) on trees, and state-transition games on permutations. Each reveals a different flavor of strategic thinking.
1. Game on Leaves — Removing the Last Leaf
Problem: You're given a tree. Two players alternately remove a leaf (a node with degree 1 in the current tree). The player who cannot make a move loses. Determine the winner given optimal play.
Note
🍃 Real-World Analogy: Imagine a tree where each leaf represents a task. Players take turns picking an outermost task (one with no remaining dependencies). The player who picks the last task wins. The strategic question: does the first player have a forced win, or can the second player always respond symmetrically?
🔍 Understanding the Game
At first glance, this seems like a simple parity game — just count the leaves and see who gets the last one. But removing a leaf can create new leaves! When you remove a leaf, its neighbor may become a new leaf. The game state evolves dynamically.
The Key Insight: Centroid
The leaf removal game has a beautiful characterization. The outcome depends on whether the tree has a centroid — a node whose removal splits the tree into subtrees each with at most n/2 nodes.
Key Insight
🔑 The Centroid Theorem: The first player wins if and only if the tree has no centroid, OR the centroid is a leaf in the initial tree. Equivalently: the first player wins iff there exists a node where removing it leaves all subtrees with size < n/2. Otherwise, the second player can mirror the first player's moves symmetrically.
📋 Edge Cases
Single node: No leaves except the node itself. Player 1 removes it and wins.
Two nodes (edge): Both nodes are leaves. Player 1 removes one, Player 2 removes the other. Player 1 loses (no move left).
Path of length n: The leaves are the two endpoints. Each move removes an endpoint, shortening the path. This is equivalent to playing on the path's length.
Star tree: One central node with k leaves. Player 1 removes a leaf, central node becomes a leaf. Player 2 removes it and wins. Second player wins for k ≥ 2.
Simplified Rule
For many competitive programming problems, the leaf-removal game reduces to counting the parity of nodes on the unique path between any two specially marked nodes. For the standard "Game on Leaves" problem:
🔍 Real-Time Thinking
"OK, so I need to figure out who wins this leaf-removal game. Let me think about the very first move. If the target node (the one I care about) is a leaf, I just remove it and win immediately. That's the trivial case.
Now if the target isn't a leaf, I need to think about parity. Every time someone removes a leaf, the tree shrinks by one node. The game has exactly n-1 moves (since the last node standing is also a leaf that gets removed). So if n is odd, there are an even number of moves — meaning the second player makes the last move. Wait, but I need to check if the target being non-leaf changes things. Yes — because the game ends when the target is removed. So the question is: can I force the target to become a leaf before my opponent removes it?"
ProblemEmbed: game-on-leaves
ProblemEmbed: deforestation
2. Tree Tag — Pursuit on a Tree
Problem: Alice and Bob are on a tree. Alice moves first. Each turn, Alice can move up to da edges, Bob can move up to db edges. Alice wants to catch Bob (occupy the same node). Bob wants to evade forever. Who wins?
Note
🏃 Real-World Analogy: Imagine a game of tag on a branching network of bridges. Alice runs faster (more edges per turn) but Bob knows the terrain. The question: given the network structure and both speeds, can Alice always corner Bob? If Alice is fast enough, the tree's diameter limits how far Bob can run.
The Distance Model
Tree tag is fundamentally a distance game. Since there's only one path between any two nodes, the game reduces to tracking the distance between Alice and Bob over time.
Analysis
Let dist(a, b) be the initial distance between Alice and Bob. The game has three key parameters:
da — Alice's speed (max edges per turn)
db — Bob's speed (max edges per turn)
D — the tree's diameter (longest shortest path)
Winning Conditions
🔍 Real-Time Thinking
"Let me think about this step by step. Alice moves first. Can she catch Bob immediately? Check da >= dist(a, b). If yes, game over — Alice wins on turn 1.
"If not, Bob runs. Bob's strategy is to always move to the farthest node from Alice. On a tree, the maximum distance is bounded by the diameter. If 2 * da >= diameter, Alice can reach any node from any other node in two moves — meaning she can always shrink the distance.
"If db > 2 * da, Bob can outrun Alice — every time Alice gets close, Bob dashes to the opposite side of the tree. He's simply too fast.
"Otherwise, it's a pure speed comparison. Alice's speed advantage determines the outcome. If da > db, Alice eventually corners Bob. If not, Bob can evade by always moving away."
ProblemEmbed: tree-tag
ProblemEmbed: game-on-tree-easy
3. Permutation Game — State Machines
Problem: Given a permutation of numbers 1 to n, two players alternately take elements from the ends (or remove elements with specific properties). The way elements are removed determines the game's outcome.
Note
🎯 Real-World Analogy: Imagine a line of numbered cards face up. Two players take turns picking cards from either end. Each card has a value. The goal is to maximize your sum — but in the permutation game variant, thepattern of picks matters. Can you force the opponent into a losing configuration?
Game States & Transitions
Permutation games are naturally modeled as state machines. Each state is a subarray (or remaining elements), and a move transitions to a smaller state. The game tree is a binary tree (take left or take right) where each node represents a remaining subarray.
Pattern: Removing From Ends
When players can only remove from the ends of a permutation, the game reduces to an interval DP — the classic "Optimal Strategy for a Game" pattern:
Pattern: Removing Arbitrary Elements
When players can remove any element from the permutation (not just ends), the game becomes about the parity of inversions or theLIS (Longest Increasing Subsequence) structure.
A common variant: players take turns removing an element. The removed sequence must be strictly increasing (or decreasing). The player who cannot make a valid move loses. This is equivalent to playing on the increasing subsequencesof the permutation.
Key Insight
🔑 Key Insight: When players can remove any element, the game outcome is determined by the parity of the longest increasing subsequence (LIS)or the number of elements that can be removed while maintaining the property. If the first player can always force a win by taking a specific element that breaks the opponent's strategy, the game reduces to a single critical choice.
The Permutation Game (CF)
A classic Codeforces variant: given a permutation of length n, players take turns. On each turn, a player removes an element. The game ends when the remaining permutation is sorted (increasing). The player who made the last move wins. This reduces to checking if the longest prefix that is already sorted has length ≥ n - 1, or more generally, analyzing the structure of the permutation's fixed points.
🔍 Real-Time Thinking
"So I have a permutation game. Let me figure out what kind it is. Can players only take from the ends? Then I use interval DP — it's a classic minimax problem where dp[l][r] tells me the score difference.
"Can players take any element? Then I need to think about the structure of the permutation. Are there elements that are already in place? How many elements can be removed before the permutation becomes sorted? The key is finding thecritical element — the one that, when removed, changes the game state fundamentally.
"For the CF permutation game variant, I notice that elements at the start that are already positioned correctly form a sorted prefix. The game is played on the remaining elements. The parity of the unsorted length tells me who makes the last move."
ProblemEmbed: permutation-game-cf
ProblemEmbed: game-on-permutation
4. Tree Strategy Patterns — Deeper Analysis
Beyond the basic leaf-removal and tag problems, trees host a rich variety of strategy games. Let's explore two more problems that appear frequently in competitive programming.
🧗 Let's Go Hiking
Problem: Alice and Bob go hiking on a mountain represented by an array of heights. Alice starts at position p. On each turn, Alice moves left to a lower position, Bob moves right to a lower position. The player who cannot move loses.
This is a tree game in disguise! The "mountain" array can be modeled as a tree where edges go from higher to lower adjacent positions. Each player has their own "movement tree" — Alice's moves go left, Bob's go right.
Key Insight
🔑 Key Insight: Since Alice can only move left and Bob only right, their games are independent! The winner is determined by comparing the length of the longest decreasing path each player can take. If Alice's longest path is strictly longer than Bob's, Alice wins. If Bob's is longer, Bob wins. If equal, Bob wins (Alice moves first, so she exhausts her moves first and Bob gets the extra turn).
ProblemEmbed: lets-go-hiking
🪓 Deforestation — The Game of Removing Subtrees
Problem: Given a rooted tree, players alternately remove a subtree (any node and all its descendants). The player who removes the root wins. This is a classic impartial combinatorial game on trees.
The solution uses Grundy numbers (also known as Nimbers) on trees. Each node's Grundy number is the XOR of (grundy[child] + 1) for all children.
Tip
⚡ Pro Tip: The "+1" in (grundy(child) + 1)accounts for the fact that when you remove a node, you can also choose to remove any subset of its children's trees. This formula is the standard "tree Nim" reduction and appears in many Tree DP + game theory problems.
ProblemEmbed: deforestation
Pattern Recognition — Tree Games Cheat Sheet
Pattern
Strategy
When to Use
Leaf Removal
Check centroid existence or parity of n
"Remove a leaf" / "Remove an endpoint"
Tree Tag
Compare speeds with diameter; check if 2*da ≥ D
"Pursuit" / "Catch" / "Tag" on a tree
Permutation Ends
Interval DP (minimax on subarrays)
"Take from either end"
Permutation Any
Analyze LIS parity or sorted prefix length
"Remove any element until sorted"
Mountain Hiking
Compare longest decreasing paths left and right
"Move only downhill in one direction"
Subtree Removal
Grundy numbers: XOR of (grundy[child] + 1)
"Remove a node and all its descendants"
🎯 Interview Cheat Sheet
Key Insight
Q1: How do I know if a tree game reduces to parity? If the game is impartial (same moves for both players) and the only relevant property is "can I make the last move?", count the total number of moves modulo 2. Key trick: if the target node is a leaf, first player wins immediately.
Key Insight
Q2: What's the most important metric in tree pursuit games? The diameter and the initial distance. If 2 * Alice's speed ≥ diameter, Alice can reach any node in 2 turns — she wins regardless of Bob's speed. If Alice's speed > Bob's speed, she eventually corners him.
Key Insight
Q3: When should I use DP vs Grundy numbers on trees? Use interval DP when players remove from ends (left/right). Use Grundy numbers when players remove arbitrary nodes or subtrees — the XOR of (grundy[child] + 1) formula handles all impartial tree games.
Key Insight
Q4: How do permutation games differ from array games? Permutations have distinct elements (1..n each exactly once), which means you can reason about inversion count, LIS length, and fixed points. Arrays can have duplicates, which changes the analysis completely.
Key Insight
Q5: What's the "Let's Go Hiking" pattern? Two players, two directions, independent movement. Compare the longest monotonic decreasing path in each direction from the starting point. Whoever has strictly more moves wins. If equal, second player wins (first player exhausts first).
📝 Key Takeaways
Tree games reduce to path analysis — unique paths between nodes make distance and parity easy to compute
Leaf removal ≡ centroid existence — if a centroid exists and isn't a special leaf, second player mirrors to win
Tree tag winner depends on diameter vs. speed — 2 * da ≥ D means Alice always wins
Bob wins if db > 2*da — strictly faster Bob can outrun Alice on any tree
Permutation games from ends → interval DP — dp[l][r] = max(perm[l] - dp[l+1][r], perm[r] - dp[l][r-1])
Permutation games (any removal) → sorted prefix length parity — unsorted segment parity determines the winner
"Hiking" style → compare longest monotonic paths — strictly longer path wins; tie favors second player
Time: O(n) or O(n²) — tree games are generally polynomial; DP variants are O(n²) for interval DP
Practice! — The only way these patterns become instinctive is by solving. The Playground is your dojo 🥋
Note
🔮 What's Next? Now that you've mastered tree and permutation games, head over to Advanced Game Strategiesfor Wythoff's Game, Flip Game, and more complex combinatorial puzzles!
// Game on Leaves — Simplified Check// If the tree has a marked node X, the winner depends on// whether X is a leaf. If X is a leaf, P1 wins by removing X// on the first move. Otherwise, parity of (n - 1) decides.function gameOnLeaves(n, edges, target) { // n = number of nodes, target = the special node (if any) // Build adjacency const adj = Array.from({ length: n + 1 }, () => []); for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); } // If target is a leaf, first player wins immediately if (adj[target].length === 1) return "First"; // Otherwise, parity of remaining moves decides // When target is not a leaf, P1 loses if n is odd (P2 mirrors) return n % 2 === 1 ? "Second" : "First";}
function treeTagWinner(n, edges, a, b, da, db) { // n = nodes, a = Alice's start, b = Bob's start // da = Alice's speed, db = Bob's speed // Returns "Alice" or "Bob" // Build adjacency const adj = Array.from({ length: n + 1 }, () => []); for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); } // BFS to find distances from Alice function bfs(start) { const dist = Array(n + 1).fill(-1); const q = [start]; dist[start] = 0; for (const u of q) { for (const v of adj[u]) { if (dist[v] === -1) { dist[v] = dist[u] + 1; q.push(v); } } } return dist; } const distFromA = bfs(a); const initialDist = distFromA[b]; // 1. Alice catches Bob on first move if (da >= initialDist) return "Alice"; // 2. Bob's speed doesn't matter if Alice is slow enough // Bob can run to the farthest leaf and stay there const distFromB = bfs(b); // Find the farthest node from Bob (diameter end) let farNode = 1; for (let i = 2; i <= n; i++) { if (distFromB[i] > distFromB[farNode]) farNode = i; } // Distance from that far node to Alice const distFromFar = bfs(farNode); const diameter = Math.max(...distFromFar.slice(1)); // 3. If Alice can reach any node within 2*da, she wins // because she can shrink Bob's safe zone every turn if (2 * da >= diameter) return "Alice"; // 4. If Bob is strictly faster than Alice, he can always evade if (db > 2 * da) return "Bob"; // 5. Otherwise, compare: if Alice can catch Bob in a game of tag // on the tree's diameter path, she wins // Core insight: Bob's effective speed is min(db, diameter) return da > db ? "Alice" : "Bob";}
// Optimal Strategy for Permutation Game (End Removal)// dp[l][r] = max net advantage current player can achieve// on subarray perm[l..r] (inclusive)function permutationGameEnds(perm) { const n = perm.length; const dp = Array.from({ length: n }, () => Array(n).fill(0)); // Base case: single element for (let i = 0; i < n; i++) { dp[i][i] = perm[i]; } // Fill DP for increasing lengths for (let len = 2; len <= n; len++) { for (let l = 0; l + len - 1 < n; l++) { const r = l + len - 1; // Take left: gain perm[l], opponent gets dp[l+1][r] // Take right: gain perm[r], opponent gets dp[l][r-1] dp[l][r] = Math.max( perm[l] - dp[l + 1][r], perm[r] - dp[l][r - 1] ); } } // Positive = first player wins, negative = second player wins return dp[0][n - 1];}
// Permutation Game (CF Variant)// Players remove elements. Game ends when permutation is sorted.// Winner = player who made the last removalfunction permutationGameCF(perm, n) { // Find how many elements at the start are already in correct position let sortedPrefix = 0; for (let i = 0; i < n; i++) { if (perm[i] === i + 1) sortedPrefix++; else break; } // If already sorted, P2 wins (no moves to make) if (sortedPrefix === n) return "Second"; // The remaining unsorted part determines the game const unsortedLen = n - sortedPrefix; // If the unsorted section has length 1, that element just needs to be // removed — P1 takes it and wins if (unsortedLen === 1) return "First"; // General case: parity of moves needed to sort via removals // In optimal play, the game reduces to who makes the last removal // If unsortedLen is odd → P1 makes last removal → P1 wins return unsortedLen % 2 === 1 ? "First" : "Second";}
function letsGoHiking(arr, p) { // arr = mountain heights, p = Alice's start (0-indexed) const n = arr.length; // Alice can only move left to lower positions let aliceMoves = 0; let pos = p; while (pos > 0 && arr[pos - 1] < arr[pos]) { aliceMoves++; pos--; } // Bob can only move right to lower positions let bobMoves = 0; pos = p; while (pos < n - 1 && arr[pos + 1] < arr[pos]) { bobMoves++; pos++; } // Alice needs strictly more moves to win if (aliceMoves > bobMoves) return "Alice"; return "Bob";}
// Deforestation — Grundy Number Solution// Grundy(node) = XOR over children of (grundy(child) + 1)function deforestationGrundy(adj, root, parent = -1) { let xor = 0; for (const child of adj[root]) { if (child === parent) continue; const childGrundy = deforestationGrundy(adj, child, root); xor ^= (childGrundy + 1); } return xor;}// If Grundy(root) !== 0, first player wins// If Grundy(root) === 0, second player wins (P-position)