BFS算法定义如下。
1. 考虑一个无向图,其顶点编号从 $$$1$$$ 到 $$$n$$$。将 $$$q$$$ 初始化为仅包含顶点 $$$1$$$ 的新队列,将顶点 $$$1$$$ 标记为已使用。
2. 从队列 $$$q$$$ 的头部提取顶点 $$$v$$$。
3. 打印顶点$$$v$$$的索引。
4. 以任意顺序迭代所有这样的顶点 $$$u$$$,$$$u$$$ 是 $$$v$$$ 的邻居,并且尚未标记为已使用。将顶点 $$$u$$$ 标记为已使用,并将其插入队列 $$$q$$$ 的尾部。
5. 如果队列不为空,则从步骤 2 继续。
6. 否则完成。
由于选择每个顶点的邻居的顺序可能不同,因此 BFS 可以打印多个序列。
在这个问题中,您需要检查给定序列是否对应于从顶点 $$$1$$$ 开始的给定树的某些有效 BFS 遍历。树是一种无向图,任何两个顶点之间都只有一条简单路径。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$),表示树中的节点数。
以下 $$$n - 1$$$ 行描述了树的边缘。它们每个都包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \le x, y \le n$$$) - 树相应边的端点。保证给定的图是一棵树。
最后一行包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) - 要检查的序列。
输出
如果序列对应于给定树的某些有效 BFS 遍历,则打印“是”(为了清楚起见,加引号),否则打印“否”(为了清楚起见,加引号)。
您可以以任何大小写(大写或小写)打印每个字母。
示例
输入 #1
4 1 2 1 3 2 4 1 2 3 4
输出 #1
Yes
输入 #2
4 1 2 1 3 2 4 1 2 4 3
输出 #2
No
注意
两个示例测试都具有相同的树。
在这棵树中,有两个有效的 BFS 排序:
- $$$1, 2, 3, 4$$$,
- $$$1, 3, 2, 4$$$.
排序 $$$1, 2, 4, 3$$$ 不对应于任何有效的 BFS 订单。