#P17211. [2025年海亮中学]好果子

    ID: 16370 传统题 6000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF2900省选/NOI-二分答案树形 DP子树转区间普通线段树最小值与次小值优化转移不变量分析

[2025年海亮中学]好果子

题目描述

陈式和司马懿在箕谷作战。

箕谷错综复杂,可以分为 nn 个区域,编号为 11 到 nn。这 nn 个区域由 n−1n-1 条双向道路连接,保证每个区域都能通过道路到达其他所有区域。

由于双方正在打仗,因此一方的军队移动之后,另一方也会立刻跟上。一开始,他们都在 rr 号区域。他们轮流行动,司马懿先手。

轮到司马懿行动时,他会沿着恰好 AA 条道路移动到另一个区域。由于道路很难走,司马懿行动时不会经过曾经走过的道路。

轮到陈式行动时,他会沿着不超过 BB 条道路移动到一个区域。可以经过 00 条道路,即留在原地。

最终,司马懿会被困住,也即他无法通过未走过的路到达一个距离恰好为 AA 的区域。

司马懿被困住后,陈式会沿着不超过 BB 条道路移动到一个区域。由于道路很难走,陈式此次移动时不会经过曾经走过的道路。

每个区域都有许多果子,第 ii 个区域的果子价值为 ii。陈式希望最后到达一个果子价值尽量小的区域,司马懿希望最后到达一个果子价值尽量大的区域。

陈式和司马懿都无限聪明。求他们最后会到达哪个区域。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 TT,表示测试数据组数。

接下来依次输入每组测试数据,对于每组测试数据:

输入的第一行包含四个正整数 n,r,A,Bn,r,A,B。

接下来 n−1n-1 行,每行包含两个整数,描述一条道路连接的两个区域。

输出格式

对于每组测试数据,输出一行一个整数,表示答案。

样例 1 输入

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

样例 1 输出

2
3

样例 1 解释

考虑第一组数据。初始两人在 66 号区域,A=2,B=1A=2,B=1。司马懿第一步可以移动到 2,3,82,3,8 号区域。

如果司马懿移动到 22 号区域,陈式可以留在原地不动。然后司马懿被困住了。陈式继续选择留在原地,于是他们最后到达了 22 号区域。

如果司马懿移动到 33 号区域,陈式可以移动到 11 号区域。然后司马懿被困住了。陈式继续选择留在原地,于是他们最后到达了 11 号区域。

如果司马懿移动到 88 号区域,陈式可以移动到 44 号区域。然后司马懿可以移动到 5,75,7 号区域。两种情况中,陈式均可以选择移动到 22 号区域。然后司马懿被困住了。陈式继续选择留在原地,于是他们最后到达了 22 号区域。

子任务

对于所有测试数据,保证 1≤T≤51\le T\le 5,1≤n≤1051\le n\le 10^5,1≤r≤n1\le r\le n,1≤A,B<n1\le A,B<n。

测试点 n≤n\le 特殊性质
1~2 10510^5 A≤BA\le B
3~6 每个区域至多与两条道路相邻,rr 号区域至多与一条道路相邻
7~8 300300 无
9~12 10310^3
13~14 5×1045\times 10^4 B≤10B\le 10
15~16 无
17~20 10510^5