P12017 [NOISG 2025 Finals] 可达性

Sheepland 是一个有 $n$ 座城市的国家。有 $n - 1$ 条道路将各对城市连接在一起。第 $j$ 条道路直接连接城市 $u[j]$ 和 $v[j]$。最初，仅使用这些道路，可以从任意一个城市到达任意一个其他城市。 Sheepland 的所有 $n - 1$ 条道路都计划进行翻修。根据翻修计划，每条道路 $j$ 将处于以下四种状态之一： 1. 双向：城市 $u[j]$ 和 $v[j]$ 的市民可以通过这条道路前往对方的城市。 2. 从城市 $u[j]$ 到城市 $v[j]$ 的单向：只有来自城市 $u[j]$ 的市民可以通过这条道路前往城市 $v[j]$。 3. 从城市 $v[j]$ 到城市 $u[j]$ 的单向：只有来自城市 $v[j]$ 的市民可以通过这条道路前往城市 $u[j]$。 4. 关闭：城市 $u[j]$ 和 $v[j]$ 的市民都不能通过这条道路前往对方的城市。 不幸的是，翻修计划丢失了！ 为了尝试恢复计划，你向每座城市的市长询问在翻修计划下从他们的城市可以到达多少座城市。第 $i$ 座城市的市长回答 $l[i]$。然而，一些市长可能提供了错误的数值。 如果存在一个序列 $c_1, c_2, c_3, \ldots, c_k$，其中 $c_1 = u$，$c_k = v$，并且对于所有 $1 \leq x \leq k - 1$，都存在一条可通行的道路从 $c_x$ 到 $c_{x+1}$，那么城市 $v$ 被认为可以从城市 $u$ 到达。特别地，每座城市都可以到达自身。 请帮助 Sheepland 确定是否存在一个翻修计划，使得每位市长报告的可到达城市数量都是正确的！

无

无

### 子任务 对于所有测试用例，输入将满足以下约束条件： - $1 \leq n \leq 5000$ - 对于所有 $1 \leq i \leq n$，有 $1 \leq l[i] \leq n$ - 对于所有 $1 \leq j \leq n - 1$，有 $1 \leq u[j], v[j] \leq n$ - 对于所有 $1 \leq j \leq n − 1$，有 $u[j] \neq v[j]$ - 最初，仅使用道路，可以从任何城市到达任何其他城市。 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分数 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $0$ | 样例 | | $1$ | $4$ | $n \leq 7$ | | $2$ | $5$ | $n \leq 15$ | | $3$ | $11$ | $l[1] = l[2] = \cdots = l[n]$ | | $4$ | $10$ | 如果存在一个翻修计划，则存在一个这样的计划没有双向道路 | | $5$ | $45$ | $n \leq 400$ | | $6$ | $25$ | 无 | ### 样例 1 解释 此样例适用于子任务 $2, 5, 6$。 请参考下方的图示。该翻修计划与所有市长报告的可到达城市数量一致。  ### 样例 2 解释 此样例适用于子任务 $2, 4, 5, 6$。 不存在一个与所有市长报告的可到达城市数量一致的翻修计划。 ### 样例 3 解释 此样例适用于子任务 $1, 2, 5, 6$。