#P18732. [正睿NOI2021训练] -2

[正睿NOI2021训练] -2

-2

有一棵 nn 个节点的树,第 ii 个节点的权值为 aia_i,初始时所有节点都是白色。

好吃选择一个起点 vv,随后好吃和邓老师轮流操作,好吃先操作。

  • 好吃每次可以停留在当前节点,或移动到一个相邻的白色节点。停留不要求当前节点是白色。
  • 邓老师每次选择一个白色节点,将其染黑。

当所有节点都被染黑时,游戏立即结束。若好吃最后位于节点 ii,则好吃得到 aia_i 分,邓老师得到 −ai-a_i 分。双方都希望自己的得分最大。

对于每个起点 v=1,2,…,nv=1,2,\ldots,n,求双方采用最优策略时好吃的最终得分。

输入格式

第一行一个正整数 nn;第二行 nn 个正整数 a1,…,ana_1,\ldots,a_n。

接下来 n−1n-1 行,每行两个整数 u,vu,v,表示树的一条无向边。

输出格式

输出一行 nn 个整数,第 ii 个表示以节点 ii 为起点时的答案。

数据范围

1≤n≤5000001\le n\le500000,1≤ai≤1091\le a_i\le10^9,1≤u,v≤n1\le u,v\le n。保证输入是一棵树。

样例 1

输入

10
8 9 7 4 5 9 6 2 6 7
3 7
7 8
3 10
9 3
5 3
3 1
8 4
5 2
5 6

输出

8 9 9 4 9 9 8 6 8 8