Background

Translated from Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection) D1T3。$\texttt{2s,0.5G}$。

2025/07/06: Added two sets of hack testdata and rejudged (contributor

Problem Description

You are given a tree with $N$ vertices. These $N$ vertices have already been partitioned into $K$ counties.

Now you need to choose a county seat for each county. Let the county that vertex $i$ belongs to be $B_i$, and let the county seats be $A_1, A_2, \cdots, A_K$ (they must be pairwise distinct). Then the following condition must hold:

• $\forall 1\le i\le N$，$\displaystyle \operatorname{dist}(i,A_{B_i})\lt \min_{j=1,j\neq B_i}^K \operatorname{dist}(i,A_j)$。

Here, $\mathrm{dist}(a,b)$ is defined as the number of edges on the simple path between $a$ and $b$.

In other words, for every vertex, its distance to the county seat of its own county must be strictly less than its distance to any other county seat.

Determine whether this can be achieved. If it can, output one valid construction.

Input Format

The first line contains two positive integers $N, K$.

The second line contains $N$ integers $B_1, B_2, \cdots, B_N$.

The next $(N-1)$ lines each contain two positive integers $u, v$, describing a tree edge $(u, v)$.

Output Format

If it is feasible, output DA (Croatian for “yes”) on the first line. On the second line, output $K$ integers, where the $i$-th integer is the county seat of the $i$-th county.

Otherwise, output NE (Croatian for “no”).

3 2
1 1 2
1 2
2 3

DA
2 3

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

NE

8 3
1 2 1 2 2 1 3 3
1 2
1 3
2 4
2 5
3 6
3 7
7 8

DA
1 2 8

Hint

Sample Explanation

The figure below shows the explanation for sample $3$.

Constraints

【Scoring】If you answer the first question correctly, you can get $40\%$ of the score. However, you must ensure the output format is correct. That is, if you only plan to answer the first question, you still need to output $K$ distinct integers in $[1, N]$ on the second line.

For $100\%$ of the testdata, it is guaranteed that $1\le B_i\le K\le N\le 2\times 10^5$, and the input is a tree.

Special property: every vertex has degree $1$ or $3$。

Translated by ChatGPT 5