#P17683. [Jboi2026]Treemax

[Jboi2026]Treemax

题目描述

给定一棵包含 nn 个顶点的树。

一部分顶点已经被赋予编号,其余顶点尚未编号。所有已经出现的编号互不相同,并且都属于 [1,n][1,n]。

最终需要给所有未编号顶点补上编号,使所有顶点上的编号恰好构成 1,2,…,n1,2,\ldots,n 的一个排列。

对于两个不同顶点 u,vu,v,定义

$$\operatorname{cost}(u,v) = \max\left\{ a_x\mid x\text{ 位于 }u\text{ 到 }v\text{ 的简单路径上} \right\}.$$

也就是说,cost⁡(u,v)\operatorname{cost}(u,v) 是 uu 到 vv 的唯一简单路径上所有顶点编号的最大值,包括两个端点。

定义整棵树的 lostness(迷失度) 为

∑1≤u<v≤ncost⁡(u,v).\sum_{1\le u<v\le n}\operatorname{cost}(u,v).

如果完全忽略当前已经固定的编号,在全部 n!n! 种顶点编号排列中,设能够取得的最小 lostness 为 min\mathrm{min}。

现在给出一部分已经固定的编号。判断能否给剩余顶点补全编号,使:

  1. 所有顶点编号构成 1,2,…,n1,2,\ldots,n 的一个排列;
  2. 已固定的编号保持不变;
  3. 最终 lostness 恰好等于全局最小值 min\mathrm{min}。

输入格式

第一行包含整数 TT,表示测试用例数。

对于每个测试用例:

n
a_1 a_2 ... a_n

其中:

  • ai=0a_i=0 表示顶点 ii 尚未编号;
  • ai≠0a_i\ne0 表示顶点 ii 已固定为编号 aia_i。

保证所有非零 aia_i 两两不同。

随后 n−1n-1 行,每行:

u v

表示树中的一条无向边。

输出格式

对于每个测试用例:

  • 若可以补全并达到全局最小 lostness,输出 YES;
  • 否则输出 NO。

数据范围

  • 1≤T≤2×1051\le T\le2\times10^5
  • 2≤n≤2×1052\le n\le2\times10^5
  • 0≤ai≤n0\le a_i\le n
  • 所有非零 aia_i 两两不同;
  • 所有测试用例的 nn 之和不超过 2×1052\times10^5。

子任务

子任务 分值 限制
1 5 总规模 S≤7S\le7
2 12 S≤20S\le20
3 23 S≤2000S\le2000
4 18 某个顶点已经被标号为 11
5 10 每个顶点度数不超过 1010
6 32 无额外限制

样例 1

输入
2
3
3 1 2
1 3
1 2
3
0 1 0
1 2
2 3

输出
NO
YES

第一个测试中,给出的编号产生的 lostness 为 99,而所有排列能够达到的最小 lostness 为 88。

第二个测试中,可以补成 [2,1,3],其 lostness 为 88。