Croatian Olympiad in Informatics
October \(3^{rd}\) 2020
„\(I\) never felt \(so\) full that \(I\) couldn’t eat one more lamb.” – Mr. Malnar
A flock of \(K\) sheep lives in a tree, a simple connected graph without a cycle. The tree contains \(N\) nodes
denoted with integers from 1 to \(N\). Each node of a tree is a home to at most one sheep. A wise shepherd
realized that, sooner or later, wolves will learn how to climb trees.
In order to protect the sheep, we need to place shepherds into some nodes such that each sheep is protected
by at least one shepherd. It is known that each shepherd protects all sheep that are closest to
him, and only them. The distance between some sheep and some shepherd is equal to the number of
nodes on a unique path between the node containing the sheep and the node containing the shepherd
(inclusive). Additionally, the shepherd can share a node with a sheep. Of course, in that case he protects
only that sheep.
Determine the minimal number of shepherds that need to placed in the nodes of a tree such that
each sheep is protected by at least one shepherd. Additionally, determine one such arrangement of
shepherds.

Subtask
Score
Constraints
1
8
\(1 \le N \le 500\,000\), every node \(x = 1\), . . . , \(n - 1\) is connected with node \(x + 1\)
2
18
\(1 \le K \le 15\), \(1 \le N \le 500\,000\)
3
23
\(1 \le N \le 2\,000\)
4
51
\(1 \le N \le 500\,000\)
3 od 8
Croatian Olympiad in Informatics
October \(3^{rd}\) 2020

The first line contains integers \(N\) and \(K\) (\(1 \le K \le N\)) from the task description.
Each of the next \(N - 1\) lines contains two integers \(a_{i}\) and \(b_{i}\) (\(1 \le a_{i}\), \(b_{i} \le N\)) which indicate that there is
an undirected edge between nodes \(a@@RISE_MATH_BLOCK_0@@i\).
The next line contains \(K\) different integers \(o_{i}\) (\(1 \le o_{i} \le N\)) that represent nodes which containing a sheep.

In the first line you should output a number \(X\) which represents the minimal number of shepherds from
the task description.
In the second line you should output \(X\) spa\(ce-se\)parated integers which represent the nodes containing
shepherds.
If there are multiple correct solutions, you may output any of them.

생성자가 기록되지 않았습니다.

출처 COCI 2019/2020 Olympiad