P11194 [COTS 2021] County Županije

Translated from [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D1T3。$\texttt{2s,0.5G}$。 2025/07/06: Added two sets of hack testdata and rejudged (contributor @[konyakest](https://www.luogu.com.cn/user/482660)). The hack testdata is in Subtask 0。

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.

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)$.

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”).

#### 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. | Subtask ID | $N\le $ | Special Property | Score | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 20 $ | None | $ 10 $ | | $ 2 $ | $ 2\, 000 $ | None | $ 25 $ | | $ 3 $ | $ 2\times 10^5 $ | Yes | $ 30 $ | | $ 4 $ | $ 2\times 10^5 $ | None | $ 35 $ | Special property: every vertex has degree $1$ or $3$。 Translated by ChatGPT 5