3440. 不见了的人口数据 (Hard)

单点时限: 3.0 sec

内存限制: 256 MB

星光镇的地图是有 个点, 条路,这些点从 编号,两两之间都可达;这 条路的长度都是

个点是居民聚居点,第 个点上有 个居民。去年的时候,星光镇政府曾经做了个人口普查,他们投入了大量的资金,获知了所有节点的 ,而获知的目的,就是为新政府大楼的选址做准备的。由于新政府大楼一定会建在一个居民聚居点上,所以星光镇政府求出了对于每个聚居点 的「政府大楼收益评估函数」:

其中 号点之间的最短距离。特别的,

新政府大楼造好了,政府自然而然地进行了一些证据销毁工作,同时「一不小心」销毁了重金得来的人口普查数据:也就是说 都丢失了。但是巧的是,所有的收益评估函数值 竟然都留存了下来。星光镇数据研究所唐纳德博士表示:「从这些函数值中,我们完全可以将所有的人口数据都反求出来。」但是唐纳德博士,虽然是一个著名的数学天才,但却很有可能是一个假博士,他这话自然不能当真。所以当星光镇政府又要造一个新的政府大楼,又要用到这些人口数据时,他们花费了巨资进行再调查。

身在异国的你听到此事后大笑不止,利用 轻轻松松地求出了

输入格式

输入具有如下形式:

第一行一个整数

接下来 行,每行两个整数 (),分别表示这 条路。这 条路都可以双向通行。两个居民聚居点之间不会有多条路相连,也不会有一条路的两端连接了同一个居民聚居点。

最后一行,用空格隔开的 个整数 ,表示收益评估函数。

数据保证答案有解,并且满足

数据规模约定:

  • 对于 Easy 档:
  • 对于 Hard 档:

输出格式

依次序输出 。如果有多解,输出任意解。

样例

Input
2
1 2
11 9
Output
9 11
Input
6
1 2
1 3
3 4
3 5
5 6
32 45 19 28 16 21
Output
0 1 2 3 4 5

13 人解决,17 人已尝试。

13 份提交通过,共有 48 份提交。

5.5 EMB 奖励。

创建: 2 年,4 月前.

修改: 2 年,4 月前.

最后提交: 1 年,6 月前.

来源: EOJ Monthly 2017.12

题目标签