4451. 蜜雪树

【题目描述】

雪王和果蝇王正在蜜雪树上快乐地遨游！为了增添乐趣，它们决定玩一个小游戏。

有 $N$ 杯蜜雪冰城构成一棵树，雪王和果蝇王最初位于点 $R$。它们轮流行动，由果蝇王先手。

- 轮到果蝇王时，它需要带着雪王沿着恰好 $A$ 条互异的边移动。

- 轮到雪王时，它需要带着果蝇王沿着至多 $B$ 条互异的边移动。

树上的每条边其实都是一根吸管。每经过一条边，它们就会喝掉其中美味的蜜雪冰城。果蝇王不希望它主动经过一个已经没有蜜雪的吸管，而雪王则不在意。

当果蝇王无法行动时，游戏进入最终阶段。此时雪王沿着至多 $B$ 条互异且都还有蜜雪的吸管移动，然后游戏结束。

果蝇王可以喝掉终点的蜜雪冰城，它希望终点的编号尽可能大。雪王则反之。请帮忙求出它们最终会停留在哪个点上吧！

【输入格式】

第一行一个整数 $c$ 表示测试点编号。特殊的，样例的测试点编号为 $0$。

第二行四个整数 $N,R,A,B$。

接下来 $n-1$ 行每行两个数表示树边。

【输出格式】

一行一个数，代表它们最终停留的节点编号。

【样例输入1】

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

【样例输出1】

2

【样例输入2】

0
7 2 3 2
2 7
7 3
3 1
1 4
4 5
5 6

【样例输出2】

3

【数据规模与约定】

本题采用捆绑测试

对于所有数据，均有 $2\le N\le 300000$。

- $A\le B$：$4$ 分，对应 $1\sim 2$ 测试点。

- 树是一条以 $R$ 为一端的链：$16$ 分，对应 $3\sim 6$ 测试点。

- $N\le 300$：$20$ 分，对应 $7\sim 11$ 测试点。

- $N\le 3000$：$12$ 分，对应 $12\sim 14$ 测试点。

- $N\le 100000，B\le 10$：$16$ 分，对应 $15\sim 18$ 测试点。

- $N\le 100000$：$24$ 分，对应 $19\sim 22$ 测试点。

- 无限制：$8$ 分，对应 $23\sim 24$ 测试点。

大样例

【来源】

luogu P11516