d1p3 (CCO Canadian_Computing_Olympiad)
Time limit: 6 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: game theory, dynamic programming, minimax, tree, graph traversal

# 2024 Canadian Computing Olympiad
# Day 1, Problem 3
# Summer Driving

**Time Limit:** 6 seconds

## Problem Description

In Ontario, there are $N$ cities numbered from 1 to $N$. There are $N - 1$ roads numbered from 1 to $N - 1$, where the $i$-th road connects city $u_i$ and city $v_i$. It is possible to travel from any city to any other city using these roads.

Alice and Bob are travelling together, starting at city $R$. To make their driving experience more interesting, they devise the following game.

Alice and Bob will alternate turns, starting with Alice. On Alice's turn, she must drive along exactly $A$ distinct roads that they have never traversed before in either direction. On Bob's turn, he must drive along up to $B$ distinct roads (possibly zero), but some of these roads may have been traversed before.

Eventually, it will be Alice's turn, but it will be impossible for her to drive along exactly $A$ distinct roads that they have never used before. When this happens, the game enters a final phase before Alice does any more driving. In this final phase, Bob drives along up to $B$ distinct roads (possibly zero) that they have never traversed before in either direction.

Alice wants to end up in a city with as large a number as possible, while Bob wants to end up in a city with a small number. What is the city that Alice and Bob end their journey in when they both play optimally?

## Input Specification

The first line of input contains four space-separated integers, $N$, $R$, $A$, and $B$ ($1 \le R, A, B \le N$).

The next $N - 1$ lines of input each contain two space-separated integers $u_i$ and $v_i$ ($1 \le u_i, v_i \le N$, $u_i \ne v_i$), describing a road.

| Marks Awarded | Bounds on $N$     | Additional Constraints                                                                       |
| :-----------: | :---------------: | :--------------------------------------------------------------------------------------------- |
|    1 mark     | $2 \le N \le 300\,000$ | $A \le B$                                                                                   |
|    4 marks    | $2 \le N \le 300\,000$ | There are at most two roads connected to any city, and at most one road connected to city $R$. |
|    5 marks    |   $2 \le N \le 300$   | No additional constraints.                                                                  |
|    3 marks    |  $2 \le N \le 3\,000$  | No additional constraints.                                                                  |
|    4 marks    | $2 \le N \le 100\,000$ | $B \le 10$                                                                                  |
|    6 marks    | $2 \le N \le 100\,000$ | No additional constraints.                                                                  |
|    2 marks    | $2 \le N \le 300\,000$ | No additional constraints.                                                                  |

## Output Specification

Output the city that Alice and Bob end their journey in, assuming they both play optimally.

## Sample Input 1

```
9 6 2 1
1 3
1 6
2 4
2 5
2 7
3 9
4 6
4 8
```

## Output for Sample Input 1

```
2
```

## Explanation of Output for Sample Input 1

On Alice's first turn, she has three options: Drive to city 2, 3, or 8.

If Alice drives to city 2, Bob can choose not to drive on any roads in his turn. Then, it will be impossible for Alice to drive along 2 distinct roads that were never traversed before, so the game enters the final phase. Bob can choose not to drive on any roads during this final phase, ending in city 2.

If Alice drives to city 3, Bob can choose to drive 1 road to city 1. Then, it will be impossible for Alice to drive along 2 distinct roads that were never traversed before, so the game enters the final phase. Bob's only option is to not drive on any roads during this final phase, ending in city 1.

If Alice drives to city 8, Bob can choose to drive 1 road to city 4. Then, Alice can drive to either city 5 or 7. In both cases, Bob can then drive 1 road to city 2. Alice can no longer drive along 2 distinct roads that were never traversed before, so the game enters the final phase. Bob can choose not to drive on any roads during this final phase, ending in city 2.

In all cases, Bob can force the game to end in city 1 or 2. Bob cannot force the game to end in city 1, so under optimal play, the game ends in city 2.

## Sample Input 2

```
7 2 3 2
2 7
7 3
3 1
1 4
4 5
5 6
```

## Output for Sample Input 2

```
3

Starter code:

Grader code:

Setup script:

Evaluation script: