← 返回题目列表

Codeforces · 70/E

E. 信息化改革

中文机器翻译题面 查看原题

虽然已经是二十一世纪了,但大众媒体在海象国还不太流行。城市从只能沿着道路行驶的信使那里获取消息。海象国的道路网络是为了能够以完全相同的方式从任何一个城市到达任何一个城市,并且道路长度相等。

北极州长决定进行信息改革。决定选择几个城市作为区域中心。维护一个区域中心每年需要 k Fishlars(当地货币)。假设区域中心始终拥有最新新闻信息。

对于每个非区域中心的城市,决定指定一个区域中心,负责向该城市通报情况。在这种情况下,维护成本将等于每年 dlen Fishlars,其中 len 是从城市到相应区域中心的距离,以需要行驶的道路数量来衡量。

你的任务是尽量减少改革的成本。

输入

第一行包含两个给定数字 n 和 k (1 ≤ n ≤ 180, 1 ≤ k ≤ 105)。

第二行包含 n - 1 个整数 di,编号从 1 开始(di ≤ di + 1, 0 ≤ di ≤ 105)。

接下来的 n - 1 行包含由道路连接的城市对。

输出

在第一行打印一年维护所需的最少 Fishlars 数量。在第二行打印n个数字,其中第i个数字代表指定给第i个城市的区域中心的编号。如果第 i 个城市本身就是区域中心,那么您应该打印数字 i。

如果该问题有多种解决方案,请打印其中任何一个。

示例

输入 #1

8 10
2 5 9 11 15 19 20
1 4
1 3
1 7
4 6
2 8
2 3
3 5

输出 #1

38
3 3 3 4 3 4 3 3