[AdditionalFile5648.zip](file://AdditionalFile5648.zip?type=additional_file)

#5648. 「PA 2014 Final」Zadanie

标签: 传统 | 时间限制: 7000 ms | 内存限制: 128 MiB |

题目描述

题目译自 PA 2014 Final Zadanie

Bajtazar 正在为一场编程竞赛准备题目。他已经写好了题面草案：

在比特托邦有 $n$ 个城市，由 $n-1$ 条双向道路连接，使得利用道路网可以在任意两个城市之间通行。经过连接两个直接相邻城市的道路需要一小时。城市从 $1$ 到 $n$ 编号。在城市 $i$ 居住着 $a_{i}$ 名居民。

明年比特托邦将举行选举。为了完全控制投票过程，比特托邦国王决定投票仅在一个城市举行。所有比特托邦的居民都将沿着最短路径前往设有投票箱的城市并进行投票。现在剩下的工作是选择举行投票的城市。这一选择取决于许多因素。特别是，对于每个城市 $i$，我们希望计算所有比特托邦居民到达城市 $i$ 所需的总时间（我们将该值记为 $b_{i}$）[...]

Bajtazar 已经为该题目准备好了极具挑战性的测试数据，但由于意外，他丢失了一半的数据。现在每个测试点仅剩下了道路连接的描述以及包含 $b_{i}$ 值的输出文件。基于这些信息，他希望能够恢复对比特托邦每个城市居民数量 $a_i$ 的设定。

输入格式

第一行包含一个整数 $n$ $(2 \leq n \leq 300000)$，表示比特托邦的城市数量。

接下来的 $n-1$ 行，每行包含两个整数 $x_{i}$ 和 $y_{i}$ $(1 \leq x_{i}, y_{i} \leq n)$，表示城市 $x_{i}$ 与城市 $y_{i}$ 之间由一条道路连接。

最后一行包含 $n$ 个整数 $b_{i}$ $(0 \leq b_{i} \leq 10^9)$。

输出格式

输出一行，包含 $n$ 个整数 $a_{i}$。数字 $a_{i}$ 应表示比特托邦第 $i$ 个城市的居民数量。对于给定的序列 $a_{i}$，在解决 Bajtazar 的题目后，应能得到输入中给出的序列 $b_{i}$。

输入数据经过精心设计，确保答案总是存在。如果存在多个正确答案，你的程序可以输出其中任意一个。

样例

输入

2
1 2
17 31

输出

31 17