P11516 [CCO 2024] Summer Driving

翻译自 [CCO](https://cemc.uwaterloo.ca/resources/past-contests?contest_category=80) 的 [2024P3题](https://dmoj.ca/problem/cco24p3)。 时限：$6 \texttt{s}$

有 $N$ 个城市，从 $1$ 号到 $N$ 号。有 $N-1$ 条道路将这些城市连成了一棵树，道路从 $1$ 号到 $N-1$ 号编号，第 $i$ 条道路连接城市 $u_i$ 和城市 $v_i$。 Alice 和 Bob 一起旅行，从城市 $R$ 出发。为了使他们的旅行更有趣，他们设计了一个游戏。Alice 和 Bob 轮流驾驶，从 Alice 开始。 在 Alice 的回合，她必须沿着**恰好** $A$ 条**他们**从未走过的道路行驶。 在 Bob 的回合，他必须沿着至多 $B$ 条道路（可能为零）行驶。 在 Alice 无法按她的方式行驶时，Bob 沿着至多 $B$ 条他们以前**从未驾驶过**的道路行驶。 Alice 想要最大化游戏结束时所在的城市编号，而 Bob 想要它最小化。那么当两人的操作都最优时，游戏结束时他们所在的城市编号是多少？

第一行四个整数，分别是 $N,R,A,B$。 往后 $N-1$ 行每行两个整数 $u_i,v_i$（$1\le u_i,v_i \le N,u_i \neq v_i$），描述一条道路。

输出 Alice 和 Bob 旅程结束时所在的城市，假设他们使用最优方式。

### 数据范围 | Subtask | 分数 | 约束 | | :----------: | :----------: | :----------: | | Subtask $1$ | $4$ | $2 \le N \le 300000$，$A \le B$ | | Subtask $2$ | $16$ | $2 \le N \le 300000$，任何城市最多有两条路连接，最多有一条路连接到城市 $R$。 | | Subtask $3$ | $20$ | $2 \le N \le 300$ | | Subtask $4$ | $12$ | $2 \le N \le 3000$ | | Subtask $5$ | $16$ | $2 \le N \le 100000$，$B\le 10$ | | Subtask $6$ | $24$ | $2 \le N \le 100000$ | | Subtask $7$ | $8$ | $2 \le N \le 300000$ | Subtask $0$ 为样例。 ### 样例解释 #1 在 Alice 的第一回合中，她有三个选择：前往城市 $2$、$3$ 或 $8$。 如果 Alice 前往城市 $2$，Bob 可以在他的回合中不走任何道路。这样一来，Alice 就无法沿两条从未走过的新道路行驶，因此游戏进入最终阶段。在最终阶段，Bob 可以选择不走任何道路，从而结束在城市 $2$。 如果 Alice 前往城市 $3$，Bob 可以选择从城市 $1$ 走一条道路。这样一来，Alice 就无法沿两条从未走过的新道路行驶，因此游戏进入最终阶段。在最终阶段，Bob 唯一的选择是不走任何道路，从而结束在城市 $1$。 如果 Alice 前往城市 $8$，Bob 可以选择从城市 $4$ 走一条道路。然后，Alice 可以前往城市 $5$ 或 $7$ 中的任意一个。在两种情况下，Bob 都可以从城市 $2$ 走一条道路。Alice 无法再沿两条从未走过的新道路行驶，因此游戏进入最终阶段。在最终阶段，Bob 可以选择不走任何道路，从而结束在城市 $2$。 在所有情况下，Bob 都可以使游戏结束在城市 $1$ 或 $2$。因此在最佳情况下，游戏结束在城市 $2$。