P12195 [NOISG 2025 Prelim] Itinerary

科学委员会计划访问 $n$ 个城市。这 $n$ 个城市通过恰好 $n - 1$ 条道路连接，使得可以使用这些道路在所有城市对之间移动。第 $i$ 条道路建在城市 $u[i]$ 和 $v[i]$ 之间。 每个城市都有自己的机场。为了开始旅程，委员会将从新加坡飞往其中一个城市。为了尽可能高效地利用旅程，委员会希望通过每条道路**恰好两次**（每个方向一次）来访问每个城市**至少一次**，然后从他们最终到达的城市飞回家。满足这个条件的旅程称为**巡游**。  例如，设上图表示一个有 $n = 8$ 个城市的地图。从城市 $1$ 开始的一种可能的巡游是 $1 \to 3 \to 5 \to 3 \to 4 \to 2 \to 8 \to 2 \to 4 \to 6 \to 4 \to 7 \to 4 \to 3 \to 1$。注意这个巡游总共访问了所有城市 $2n - 1$ 次（等于 $15$），并且以起始城市（城市 $1$）结束。可以证明，对于所有可能的城市地图，所有巡游都满足这两个性质。 委员会还希望访问 $m$ 个按顺序从事件 $1$ 到事件 $m$ 发生的活动。事件 $j$ 将在城市 $s[j]$ 举行。一个城市可以举办零个、一个或多个活动，但不会有两个连续的活动在同一个城市举行，即 $s[j] = s[j + 1]$。 允许委员会访问所有活动的巡游必须按顺序访问城市 $s[1], s[2], \ldots, s[m]$，但不必连续。这样的巡游称为**行程**。形式上，设 $t[1], t[2], \ldots, t[2n - 1]$ 为某个巡游访问的城市序列。当且仅当 $s$ 是 $t$ 的一个子序列时，该巡游是一个行程。也就是说，可以通过删除 $t$ 中的零个或多个元素并保持剩下元素的顺序，得到 $s$。仍以上面的例子为例，假设 $m = 4$ 且 $s = [3, 5, 2, 7]$，那么巡游 $1 \to \textbf{3} \to \textbf{5} \to 3 \to 4 \to \textbf{2} \to 8 \to 2 \to 4 \to 6 \to 4 \to \textbf{7} \to 4 \to 3 \to 1$ 是一个行程，因为城市 $3, 5, 2, 7$ 按顺序在巡游中被访问（用粗体标记并下划线）。 委员会仍在决定从哪个城市出发，但他们同意：如果存在某个以该城市出发的行程，那么该城市就是一个好的出发选择。请帮助委员会判断对于所有城市，是否存在至少一个以该城市出发的行程。

无

无

### 子任务 对于所有测试用例，输入将满足以下约束条件： - $2 \leq n \leq 200\,000$ - $1 \leq m \leq 2n - 1$ - $1 \leq u[i], v[i] \leq n$ 对所有 $1 \leq i \leq n - 1$ - $1 \leq s[j] \leq n$ 对所有 $1 \leq j \leq m$ - $s[j] \neq s[j + 1]$ 对所有 $1 \leq j \leq m - 1$ - 可以通过道路在所有城市对之间移动。 你的程序将在满足以下特殊性质的输入数据上进行测试： | 子任务 | 分值 | 特殊性质 | | :-: | :-: | :-: | | $0$ | $0$ | 样例 | | $1$ | $7$ | $n \leq 1000, m = 2n - 1$ | | $2$ | $10$ | $u[i] = 1, v[i] = i + 1$ | | $3$ | $6$ | $n \leq 1000, u[i] = i, v[i] = i + 1$ | | $4$ | $7$ | $u[i] = i, v[i] = i + 1$ | | $5$ | $14$ | $n \leq 1000, m \leq 10$ | | $6$ | $5$ | $n \leq 1000$ | | $7$ | $19$ | $m \leq 10$ | | $8$ | $11$ | $s[1] = s[m]$ | | $9$ | $21$ | 无 | ### 样例 1 解释 此样例适用于子任务 $5, 6, 7, 9$。 这个样例在题目中已经作为示例说明。 存在以城市 $1, 3, 4, 6$ 和 $7$ 开始的行程。在题目中已给出一个以城市 $1$ 开始的行程。 另一方面，可以证明城市 $2, 5$ 和 $8$ 没有任何行程可以以它们为起点。 ### 样例 2 解释 此样例适用于子任务 $5, 6, 7, 9$。 这个测试用例与题目示例相同，除了 $s[2]$ 和 $s[3]$ 被交换了。此时不存在任何行程。 ### 样例 3 解释 此样例适用于子任务 $1, 2, 5, 6, 7, 8, 9$。 ### 样例 4 解释 此样例适用于子任务 $3, 4, 5, 6, 7, 9$。