Problem K. Interesting Vertices

时间限制 2000 ms   内存限制 256 MB

You are given a tree with $$$n$$$ vertices. A tree is a connected graph without any cycles. The vertices are indexed from $$$1$$$ to $$$n$$$.

$$$k$$$ vertices are colored (more specifically, the colored vertices have indices $$$a_1, a_2, \dots, a_k$$$). We can choose any uncolored vertex $$$x$$$ and root the tree at it, so we can assume that $$$x$$$ is the root of the tree. Let's analyze all the subtrees of the given tree such that the roots of these subtrees are the children of root vertex $$$x$$$. If each of these subtrees contains at least one colored vertex, then $$$x$$$ is an interesting vertex.

Your task is to find all interesting vertices in the given tree and print their indices in ascending order.

输入数据

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(2 \le n \le 2 \cdot 10^{5}, 1 \le k < n)$$$ — the total number of vertices in the tree and the number of colored vertices, respectively.

The second line contains a sequence of distinct integers $$$a_1, a_2, \dots, a_k$$$ $$$(1 \le a_i \le n)$$$ — the indices of the colored vertices.

Next $$$n - 1$$$ lines denote the edge of the tree, each line contains two integers $$$u_j$$$ and $$$v_j$$$ $$$(1 \le u_j, v_j \le n, u_j \neq v_j)$$$ representing an edge between these two vertices. It is guaranteed that these edges form a tree.

输出数据

In the first line print $$$p$$$ — the number of interesting vertices.

In the second line print $$$p$$$ distinct integers — the indices of interesting vertices. Each interesting vertex should be printed exactly once. The indices should be sorted in ascending order.

样例

样例说明

In the first example there are three uncolored vertices, and only vertex $$$2$$$ is not an interesting vertex, since it is connected to three other vertices, but only one of these vertices contains a colored vertex in its subtree.

提交

请先 登录

© 2025 FAQs Contact About