← 返回题目列表

Codeforces · 1324/F

F. 最大白色子树

中文机器翻译题面 查看原题

给你一棵由 $$$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$$$组成的子树。