Migrated from Lutece 2779 矿物储量不足

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Frisky星上有$n$个节点，这些节点被$n-1$条通道互相连通。这些节点可能为水晶矿脉节点或者异虫巢穴节点。现在Liar想尽可能多的获取这颗星球上的资源。Liar可以在节点$k$上建立指挥中心，并占领包含节点$k$的一个连通块，在占领的连通块内(包括$k$)的每个水晶矿脉节点会为Liar提供$1$点资源，每个异虫巢穴节点会使Liar损失1点资源。现在Liar已经知道了这些节点的连通情况，Liar会非常高兴如果你能快速地告诉他在任意一个节点上建立指挥中心能获取的最大资源量。

Input

第1行包含一个整数$n (2≤ n ≤ 2e5)$，表示节点个数。 第2行包含n个整数$c1,c2,...,cn (0≤ n ≤ 1)$，其中$ci$为1表示节点i为水晶矿脉节点，为0表示节点i为异虫巢穴节点。 第3~n+1行每行包含两个整数$ui,vi (1≤ ui,vi ≤ n)$，表示相连通的两个节点。

Output

输出$n$个整数$a1,a2,...,an$，其中$ai$表示在节点$i$上建立指挥中心获取的最大资源量。

Samples

8
1 0 1 0 1 1 0 0
1 2
1 3
2 4
2 5
3 6
3 7
7 8

3 3 3 2 3 3 2 1

Resources

2022 UESTC ICPC Training for Dynamic Programming