CF 1970C2 - Game on Tree (Medium)

CF 1970C2 - Game on Tree (Medium)

Rating: 1700
Tags: dfs and similar, dp, games, trees
Solve time: 2m
Verified: yes

Solution

Problem Understanding

We are given a tree where every node is initially unused. A single stone is placed on a chosen starting node. From that moment, players alternate moves, starting with Ron. A move consists of sliding the stone along an edge to a neighboring node that has never been visited before. Once the stone enters a node, that node becomes unusable for future moves. The game stops when the stone is stuck, meaning all neighbors of the current node have already been visited.

Since the structure is a tree, revisiting nodes is impossible in a meaningful way, because every move strictly goes to a fresh node. So the play always traces a simple path that grows until it hits a leaf in the remaining unvisited portion.

The outcome depends only on the parity of how many moves can be made starting from the initial node. If the number of moves is odd, Ron makes the last move and wins. If it is even, Hermione makes the last move and wins.

The input size reaches up to 200000 nodes, which immediately rules out any per-query traversal that revisits large parts of the tree. Even a single DFS per query is fine here because there is only one starting node, so an O(n) solution is acceptable. Any solution must compute a structural property of the tree rather than simulate gameplay.

A subtle failure case appears when thinking in terms of “distance to leaf”. In a tree, multiple branches exist, and the game does not always follow the longest path globally, but instead depends on the best continuation from the starting node, which corresponds to the longest downward path in any direction.

Example of confusion:

Input

3 1
1 2
1 3
2

From node 2, only one move exists, so Ron wins immediately. A mistaken idea that global diameter matters would incorrectly predict otherwise.

Another edge case is a linear chain. Starting near the middle changes parity depending on direction choices, but optimal play always extends the path deterministically to maximize survival, which again ties back to longest reachable depth, not arbitrary branching.

Approaches

A brute-force simulation would start at the chosen node and recursively try all possible moves, alternating turns, computing whether the current player has a winning move. This is essentially a DFS over game states, where each state is determined by the current node and the set of visited nodes. Since visited states differ by path history, the state space explodes exponentially. In a chain of length n, the number of possible prefixes is already linear, but branching in a tree increases it drastically, leading to exponential behavior in the worst case.

The key observation is that the visited set is always exactly the simple path from the starting node to the current node. There is never a choice that revisits or branches backward. So the game is not a general graph game but a deterministic path extension game.

From any node, the remaining play length is simply the maximum number of edges you can still traverse without revisiting nodes, which is exactly the depth of the deepest descendant if we root the tree at the starting node. Each move reduces this remaining depth by 1, so the winner is determined by whether this depth is odd or even.

Thus the problem reduces to computing, for the chosen root, the longest path downward in any direction, which is equivalent to the maximum distance from the starting node to any leaf in the tree.

Algorithm Walkthrough

We treat the starting node as a root and compute the longest distance from it to any node in the tree using DFS.

1. Build the adjacency list representation of the tree. This allows O(1) neighbor traversal.
2. Run a DFS starting from the given initial node, tracking parent to avoid going backward. This DFS computes the maximum distance from the start node to any reachable node.
3. For each node visited, recursively compute the maximum depth among its children as 1 + child_depth. This captures how many moves can still be made if the stone is currently at that node.
4. The result of the DFS at the starting node gives the total number of moves available in an optimal play sequence.
5. If this number is odd, Ron wins because he makes the first move and also the last move. If it is even, Hermione wins.

Why it works

The game never branches in a way that changes the remaining reachable structure except by removing the current node from future consideration. Since the graph is a tree, removing visited nodes leaves a connected subtree that always contains exactly one extension from the current position along any simple path. Therefore, optimal play always extends the longest possible continuation, which is equivalent to a longest path in the rooted tree. The parity of that path length fully determines the winner because players alternate moves along a forced sequence.

Python Solution

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n, t = map(int, input().split())
adj = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    u, v = map(int, input().split())
    adj[u].append(v)
    adj[v].append(u)

start = int(input())

def dfs(u, p):
    best = 0
    for v in adj[u]:
        if v == p:
            continue
        best = max(best, 1 + dfs(v, u))
    return best

moves = dfs(start, -1)

if moves % 2 == 1:
    print("R