#P17683. [Jboi2026]Treemax
[Jboi2026]Treemax
题目描述
给定一棵包含 个顶点的树。
一部分顶点已经被赋予编号,其余顶点尚未编号。所有已经出现的编号互不相同,并且都属于 。
最终需要给所有未编号顶点补上编号,使所有顶点上的编号恰好构成 的一个排列。
对于两个不同顶点 ,定义
$$\operatorname{cost}(u,v) = \max\left\{ a_x\mid x\text{ 位于 }u\text{ 到 }v\text{ 的简单路径上} \right\}.$$也就是说, 是 到 的唯一简单路径上所有顶点编号的最大值,包括两个端点。
定义整棵树的 lostness(迷失度) 为
如果完全忽略当前已经固定的编号,在全部 种顶点编号排列中,设能够取得的最小 lostness 为 。
现在给出一部分已经固定的编号。判断能否给剩余顶点补全编号,使:
- 所有顶点编号构成 的一个排列;
- 已固定的编号保持不变;
- 最终 lostness 恰好等于全局最小值 。
输入格式
第一行包含整数 ,表示测试用例数。
对于每个测试用例:
n
a_1 a_2 ... a_n
其中:
- 表示顶点 尚未编号;
- 表示顶点 已固定为编号 。
保证所有非零 两两不同。
随后 行,每行:
u v
表示树中的一条无向边。
输出格式
对于每个测试用例:
- 若可以补全并达到全局最小 lostness,输出
YES; - 否则输出
NO。
数据范围
- 所有非零 两两不同;
- 所有测试用例的 之和不超过 。
子任务
| 子任务 | 分值 | 限制 |
|---|---|---|
| 1 | 5 | 总规模 |
| 2 | 12 | |
| 3 | 23 | |
| 4 | 18 | 某个顶点已经被标号为 |
| 5 | 10 | 每个顶点度数不超过 |
| 6 | 32 | 无额外限制 |
样例 1
输入
2
3
3 1 2
1 3
1 2
3
0 1 0
1 2
2 3
输出
NO
YES
第一个测试中,给出的编号产生的 lostness 为 ,而所有排列能够达到的最小 lostness 为 。
第二个测试中,可以补成 [2,1,3],其 lostness 为 。