CF1037D.Valid BFS?

The BFS algorithm is defined as follows.

1. Consider an undirected graph with vertices numbered from $1$ to $n$. Initialize $q$ as a new queue containing only vertex $1$, mark the vertex $1$ as used.
2. Extract a vertex $v$ from the head of the queue $q$.
3. Print the index of vertex $v$.
4. Iterate in arbitrary order through all such vertices $u$ that $u$ is a neighbor of $v$ and is not marked yet as used. Mark the vertex $u$ as used and insert it into the tail of the queue $q$.
5. If the queue is not empty, continue from step 2.
6. Otherwise finish.

Since the order of choosing neighbors of each vertex can vary, it turns out that there may be multiple sequences which BFS can print.

In this problem you need to check whether a given sequence corresponds to some valid BFS traversal of the given tree starting from vertex $1$. The tree is an undirected graph, such that there is exactly one simple path between any two vertices.

BFS 算法定义如下：

1. 考虑一个顶点编号为 $1$ 到 $n$ 的无向图。初始化一个新队列 $q$，其中仅包含顶点 $1$，并将顶点 $1$ 标记为已访问。
2. 从队列 $q$ 的队首取出一个顶点 $v$。
3. 输出顶点 $v$ 的编号。
4. 以任意顺序遍历所有满足以下条件的顶点 $u$：$u$ 是 $v$ 的邻接顶点，且尚未被标记为已访问。将顶点 $u$ 标记为已访问，并将其插入队列 $q$ 的队尾。
5. 若队列非空，则返回步骤 2 继续执行。
6. 否则算法结束。

由于在遍历每个顶点的邻接顶点时顺序可以任意选择，因此 BFS 可能输出多种不同的序列。

本题中，你需要判断给定的序列是否对应于以顶点 $1$ 为起点、对给定树所进行的某次合法 BFS 遍历。所谓树，是指一种无向图，其中任意两个顶点之间恰好存在唯一一条简单路径。

The first line contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) which denotes the number of nodes in the tree.

The following $n - 1$ lines describe the edges of the tree. Each of them contains two integers $x$ and $y$ ($1 \le x, y \le n$) — the endpoints of the corresponding edge of the tree. It is guaranteed that the given graph is a tree.

The last line contains $n$ distinct integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le n$) — the sequence to check.

第一行包含一个整数 $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$），即待检验的序列。

Print "Yes" (quotes for clarity) if the sequence corresponds to some valid BFS traversal of the given tree and "No" (quotes for clarity) otherwise.

You can print each letter in any case (upper or lower).

如果该序列对应于给定树的某个有效的 BFS 遍历，则输出 "Yes"（引号仅用于明确显示）；否则输出 "No"（引号仅用于明确显示）。

每个字母可使用任意大小写形式输出（大写或小写均可）。

Both sample tests have the same tree in them.

In this tree, there are two valid BFS orderings:

• $1, 2, 3, 4$,
• $1, 3, 2, 4$.

The ordering $1, 2, 4, 3$ doesn't correspond to any valid BFS order.

两个样例测试用例中包含相同的树。

在此树中，存在两种合法的 BFS 遍历顺序：

• $1, 2, 3, 4$，
• $1, 3, 2, 4$。

而顺序 $1, 2, 4, 3$ 并不对应任何合法的 BFS 遍历顺序。