3749: 大陆(第四轮03)

欧艾大陆由 n  个城市组成，呈树形结构。每一个城市就是一个树上的顶点， 由 无向边相连。

为了方便管理，国王 crying  希望能够将欧艾大陆的城市分成若干个省，使得每 个城市都恰好在一个省内。

crying  是一个理智的人， 经过精密的统计和计算， 他认为每个省应该满足以下 条件：

- 不能包含太多或太少的城市：即大小应该在  [B, 3 × B]   内，其中  B  是一个给 定的参数。

- 需要指定一个城市作为这个省的省会，与地球人的常识不同，这个省的省会可 以不属于这个省，且一个城市可以作为多个省的省会，但是对于每个城市 x，如 果该城市所属于的省的省会是 y， 那么  (x, y)  之间的简单路径上的所有点都要 满足和 x  在同一个省。

你作为国王的首席智囊团，需要帮助他找到一组满足条件的划分方法。 如果有多组划分方案，只需要其中一组即可。

数据保证存在至少一种划分方案。

接下来 n − 1  行，每行两个正整数  x, y，描述一条边。

第一行一个正整数 `k`，表示将图划分成的省的个数。

第二行 n  个数  a1  , a2  , … , an ， ai  表示第  i  个城市属于哪一个省。 第三行 k  个数 b1, b2 , … , b k， bi  表示第 i  个省的省会城市。

请保证 k ≤ n，可以证明，必然存在一种 k ≤ n  的划分方案。

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

3
2 1 1 3 3 3 3 2
2 1 8