| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 6 초 | 1024 MB | 6 | 1 | 1 | 100.000% |
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?
The first line of input contains four space-separated integers, $N,ドル $R,ドル $A,ドル and $B$ (1ドル ≤ R, A, B ≤ N$).
The next $N - 1$ lines of input each contain two space-separated integers $u_i$ and $v_i$ (1ドル ≤ u_i, v_i ≤ N,ドル $u_i \ne v_i$), describing a road.
Output the city that Alice and Bob end their journey in, assuming they both play optimally.
| Subtask | Score | Bounds on $N$ | Additional constraints |
|---|---|---|---|
| 1 | 1 | 2ドル ≤ N ≤ 300,円 000$ | $A ≤ B$ |
| 2 | 4 | 2ドル ≤ N ≤ 300,円 000$ | There are at most two roads connected to any city, and at most one road connected to city $R$. |
| 3 | 5 | 2ドル ≤ N ≤ 300$ | No additional constraints. |
| 4 | 3 | 2ドル ≤ N ≤ 3,円 000$ | No additional constraints. |
| 5 | 4 | 2ドル ≤ N ≤ 100,円 000$ | $B ≤ 10$ |
| 6 | 6 | 2ドル ≤ N ≤ 100,円 000$ | No additional constraints. |
| 7 | 2 | 2ドル ≤ N ≤ 300,円 000$ | No additional constraints. |
9 6 2 1 1 3 1 6 2 4 2 5 2 7 3 9 4 6 4 8
2
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ドル$.
7 2 3 2 2 7 7 3 3 1 1 4 4 5 5 6
3