← 返回题目列表

Codeforces · 1794/E

E. 用距离标记树

中文机器翻译题面 查看原题

给你一棵由 $$$n$$$ 顶点组成的未加权树,编号从 $$$1$$$ 到 $$$n$$$ 以及 $$$n-1$$$ 整数 $$$a_1, a_2, \ldots, a_{n-1}$$$ 的列表。树是无环的连通无向图。您将使用列表中的每个元素来标记一个顶点。任何顶点不应被标记两次。您可以使用任何整数来标记唯一剩余的未标记顶点。

如果可以进行此标记,使得对于每个顶点 $$$i$$$,其标签是 $$$x$$$ 和 $$$i$$$ 之间的距离,则顶点 $$$x$$$ 被称为良好。树上两个顶点 $$$s$$$ 和 $$$t$$$ 之间的距离是从顶点 $$$s$$$ 开始到顶点 $$$t$$$ 结束的路径上的最小边数。

找到所有好的顶点。

输入

第一行包含一个整数 $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — 树中的顶点数。

第二行包含 $$$n - 1$$$ 整数 $$$a_1,a_2,\ldots,a_{n-1}$$$ ($$$0\le a_i < n$$$) — 给定列表。

然后是 $$$n−1$$$ 行。它们每个都包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$) 表示顶点 $$$u$$$ 和 $$$v$$$ 之间的边。保证边形成一棵树。

输出

在第一行打印良好顶点的数量。

在第二行中,按升序打印所有好顶点的索引。

示例

输入 #1

6
2 1 0 1 2
1 2
2 3
2 4
4 5
4 6

输出 #1

2
2 4

输入 #2

5
1 2 1 2
1 2
3 2
3 4
5 4

输出 #2

1
3

输入 #3

3
2 2
1 2
2 3

输出 #3

0

注意

这是第一个示例的树:

这是列表上元素的两个可能的标签,因此 $$$2$$$ 是一个好的顶点(左),$$$4$$$ 是一个好的顶点(右)。

每个顶点下方的方块代表其标签。黑色方块包含给定列表中的数字,唯一的白色方块包含唯一不在给定列表中的数字。

在第二个示例中,唯一好的顶点是顶点 $$$3$$$。

在第三个示例中,没有好的顶点。