最大白色连通子树 - 代码源竞赛平台

题目描述

蜗蜗有一棵包含 $n$ 个节点的树，节点编号为 $1$ 到 $n$。每个节点的颜色都是白色或黑色。

蜗蜗可以从树中选出一些节点，要求这些节点连同它们之间的边构成一个连通子图。这个连通子图的得分等于其中白色节点的数量减去黑色节点的数量。

对于每个节点 $v$，请你分别求出所有包含节点 $v$ 的连通子图中，能够获得的最大得分。不同节点的答案彼此独立。

输入格式

第一行包含一个整数 $n$，表示节点数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。当 $a_i=1$ 时，节点 $i$ 为白色；当 $a_i=0$ 时，节点 $i$ 为黑色。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 与节点 $v$ 之间有一条无向边。

输出格式

输出一行 $n$ 个整数，第 $v$ 个整数表示包含节点 $v$ 的连通子图能够获得的最大得分。

样例

3
1 0 1
1 2
2 3

1 1 1

样例解释

选择整棵树，可以得到一个包含两个白色节点和一个黑色节点的连通子图，得分为 $2-1=1$。

这个连通子图包含每个节点，而这三个节点各自能够获得的最大得分都为 $1$。

数据范围

对于 100% 的数据，保证 $2\le n\le 2\times 10^5$，$a_i\in\{0,1\}$，$1\le u,v\le n$。

输入的边构成一棵树。