P11194 [COTS 2021] 县 Županije

译自 [Izborne Pripreme 2021 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2021/) D1T3。$\texttt{2s,0.5G}$。 2025/07/06：加入两组 Hack 数据并进行了重测（贡献者 @[konyakest](https://www.luogu.com.cn/user/482660)），Hack 数据位于 Subtask 0。

给定 $N$ 个点的树。已经将这 $N$ 个点划分成了 $K$ 个县。 现在你要为每个县确定一个**县城**。设第 $i$ 个点属于的县为 $B_i$，每个县的县城为 $A_1,A_2,\cdots,A_K$（必须两两不同），则下列关系式必须满足： - $\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)$。 其中，$\mathrm{dist}(a,b)$ 定义为 $a,b$ 之间简单路径的边数。 也就是说，每个县中的点到它所属的县城距离必须**严格小于**到其它县城的距离。 判断这是否是可以达成的。如果可以的话，需要给出一组符合条件的方案。

第一行，两个正整数 $N,K$。 第二行，$N$ 个整数 $B_1,B_2,\cdots,B_N$。 接下来 $(N-1)$ 行，每行两个正整数 $u,v$，描述一条树边 $(u,v)$。

如果可行的话，第一行输出 `DA`（克罗地亚语「是」）；第二行 $K$ 个整数，第 $i$ 个整数表示第 $i$ 个县的县城。 否则输出 `NE`（克罗地亚语「否」）。

#### 样例解释 下图是样例 $3$ 的解释。  #### 数据范围 【评分方式】如果你回答对了第一问，可以获得 $40\%$ 的分数。但是需要保证输出格式正确，即，如果只打算回答第一问，也要在第二行输出 $K$ 个不同的 $\in [1,N]$ 的整数。 对于 $100\%$ 的数据，保证 $1\le B_i\le K\le N\le 2\times 10^5$，给出的是一棵树。 | 子任务编号 | $N\le $ | 特殊性质 | 得分 | | :--: | :--: | :--: | :--: | | $ 1 $ | $ 20 $ | 无 | $ 10 $ | | $ 2 $ | $ 2\, 000 $ | 无 | $ 25 $ | | $ 3 $ | $ 2\times 10^5 $ | 有 | $ 30 $ | | $ 4 $ | $ 2\times 10^5 $ | 无 | $ 35 $ | 特殊性质：每个点的度数为 $1$ 或 $3$。