给你一棵由 $$$n$$$ 个顶点组成的树。树是一个具有 $$$n-1$$$ 边的无向连通图。该树的每个顶点 $$$v$$$ 都分配有一个颜色(如果顶点 $$$v$$$ 为白色,则 $$$a_v = 1$$$;如果顶点 $$$v$$$ 为黑色,则 $$$0$$$)。
你必须为每个顶点$$$v$$$解决以下问题:如果你选择给定树中包含顶点$$$v$$$的子树,你可以获得的白色顶点数和黑色顶点数之间的最大差是多少?树的子树是给定树的连通子图。更正式地说,如果您选择包含 $$$cnt_w$$$ 白色顶点和 $$$cnt_b$$$ 黑色顶点的子树,则必须最大化 $$$cnt_w - cnt_b$$$。
输入
输入的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 树中的顶点数。
输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 1$$$),其中 $$$a_i$$$ 是第 $$$i$$$ 个顶点的颜色。
接下来的 $$$n-1$$$ 行描述了树的一条边。边 $$$i$$$ 由两个整数 $$$u_i$$$ 和 $$$v_i$$$ 表示,它连接的顶点的标签 $$$(1 \le u_i, v_i \le n, u_i \ne v_i$$$)。
保证给定的边形成一棵树。
输出
打印 $$$n$$$ 整数 $$$res_1, res_2, \dots, res_n$$$,其中 $$$res_i$$$ 是包含顶点 $$$i$$$ 的某些子树中白色和黑色顶点数量之间的最大可能差异。
示例
输入 #1
9 0 1 1 1 0 0 0 0 1 1 2 1 3 3 4 3 5 2 6 4 7 6 8 5 9
输出 #1
2 2 2 2 2 1 1 0 2
输入 #2
4 0 0 1 0 1 2 1 3 1 4
输出 #2
0 -1 1 -1
注意
第一个示例如下所示:
黑色顶点有粗体边框。
在第二个示例中,顶点$$$2、3$$$和$$$4$$$的最佳子树相应地是顶点$$$2、3$$$和$$$4$$$。顶点$$$1$$$的最佳子树是由顶点$$$1$$$和$$$3$$$组成的子树。