题目北京

Banana 的爱好是种树，尤其喜欢种香蕉树~

题目描述

Banana 的香蕉树由 \(n\) 个分叉点和 \(n-1\) 条树枝组成，可以看作是一个 \(n\) 个点 \(n-1\) 条边的无向连通图。

Banana 花园的土地很神奇，富含有极高的营养成分，这些营养会被树根吸收，然后沿着树枝传递到各个分叉点。但是营养在传递过程中会损耗。具体的，令 \(rt\) 为根节点，\(d(x,y)\) 表示 \(x\) 到 \(y\) 要经过的树枝数，则分叉点 \(x\) 会获得 \(C-d(rt,x)\) 点营养。

在丰富营养的滋养下，每天树上都会长满香蕉。假设分叉点 \(i\) 获得了 \(c_i\) 点营养，则这个点上会长 \(a_i\times c_i\) 根香蕉。

现在 Banana 想知道每天树上总共会长多少根香蕉。然而由于香蕉树太大了，Banana 不知道那个是根，所以他想知道对于每个 \(i\in [1,n]\)，如果分叉点 \(i\) 是根的话，一天会长多少根香蕉？

输入格式

第一行两个整数 \(n,C\)。

第二行 \(n\) 个整数，第 \(i\) 个数是 \(a_i\)。

接下来 \(n-1\) 行，每行两个整数 \(x,y\)，表示一条连接分叉点 \(x\) 和 \(y\) 的树枝。数据保证所有树枝会形成一棵树。

输出格式

共 \(n\) 行，第 \(i\) 行表示以分叉点 \(i\) 为根时一天长的香蕉数。

样例

输入样例 #1

4 4
1 2 3 4
1 2
1 3
2 4

输出样例 #1

27
29
23
27

数据范围

\(1\leq n\leq 10^5\)，\(n\leq C\leq 10^6\)，\(0\leq a_i\leq 10^7\)