题目描述

吉丽YY了一道神题，题面是这样的： “一棵 $n$ 个点的树，每条边长度为 $1$，第 $i$ 个结点居住着 $a[i]$ 个人。假设在 $i$ 结点举行会议，所有人都从原住址沿着最短路径来到 $i$ 结点，行走的总路程为 $b[i]$。输出所有 $b[i]$。”

吉丽已经造好了数据，但熊孩子把输入文件中所有 $a[i]$ 给删掉了。你能帮他恢复吗？

输入格式

第一行一个整数 $n$$(2≤n≤300000)$。 接下来 $n-1$ 行，每行两个整数 $x,y$，表示 $x$ 和 $y$ 之间有连边。 接下来一行由空格隔开的 $n$ 个整数 $b[i]$$(0≤b[i]≤10^9)$。

输出格式

输出一行由空格隔开的 $n$ 个整数 $a[i]$。 如果你觉得有多组解就任意输出其中一组,如果你觉得只有一组解就输出这组解了。

输入样例

2
1 2
17 31

输出样例

31 17

鸣谢 Jcvb 提供题目。