Snowy Mountain

Description:

Input:

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$n$$$ integers $$$l_1, l_2, \ldots, l_n$$$ ($$$0 \le l_i \le 1$$$). If $$$l_i = 1$$$, location $$$i$$$ is a base lodge; if $$$l_i = 0$$$, location $$$i$$$ is not a base lodge. It is guaranteed that there is at least $$$1$$$ base lodge.

Each of the next $$$n-1$$$ lines contains two integers $$$u, v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$), meaning that there is a trail that connects the locations $$$u$$$ and $$$v$$$. It is guaranteed that the given trails form a tree.

Output:

Print $$$n$$$ integers: the $$$i$$$-th integer is equal to the length of the longest sequence of trails that the skier starting at location $$$i$$$ can ski along without their kinetic energy ever becoming negative.

Sample Input:

6
1 1 0 0 0 0
1 3
2 4
3 4
4 5
5 6

Sample Output:

0 0 1 1 3 5 

Sample Input:

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

Sample Output:

5 3 2 1 1 1 0 0 0 

Sample Input:

14
0 0 0 0 0 0 0 0 0 1 1 1 1 1
1 2
2 5
3 4
4 5
3 6
4 8
5 9
7 8
6 11
7 12
8 13
9 14
10 11

Sample Output:

8 5 4 3 2 2 1 1 1 0 0 0 0 0 

Sample Input:

20
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 0 1
17 3
11 12
6 10
18 19
8 14
16 20
5 3
2 11
7 10
2 15
8 3
3 15
9 16
7 13
16 1
19 2
2 16
6 1
4 17

Sample Output:

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

Note:

In the first test, $$$h = [0, 0, 1, 1, 2, 3]$$$. The skier starting from $$$6$$$ can ski along at most $$$5$$$ trails, in the path $$$6 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 2$$$ (notice that a skier can ski multiple times along the same trail and can visit more than once the same location):

• at the location $$$6$$$, the kinetic energy is $$$0$$$;
• at the location $$$5$$$, the kinetic energy increases by $$$1$$$ (because $$$h_5 < h_6$$$), so it becomes $$$1$$$;
• at the location $$$4$$$, the kinetic energy increases by $$$1$$$ (because $$$h_4 < h_5$$$), so it becomes $$$2$$$;
• at the location $$$3$$$, the kinetic energy decreases by $$$1$$$ (because $$$h_3 = h_4$$$), so it becomes $$$1$$$;
• at the location $$$4$$$, the kinetic energy decreases by $$$1$$$ (because $$$h_4 = h_3$$$), so it becomes $$$0$$$;
• at the location $$$2$$$, the kinetic energy increases by $$$1$$$ (because $$$h_2 < h_4$$$), so it becomes $$$1$$$.

There isn't any sequence of trails of length greater than $$$5$$$ such that the kinetic energy is always non-negative.

Moreover,

• the optimal path for the skier starting from $$$1$$$ is $$$1$$$ (no trails);
• the optimal path for the skier starting from $$$2$$$ is $$$2$$$ (no trails);
• the optimal path for the skier starting from $$$3$$$ is $$$3 \rightarrow 1$$$;
• the optimal path for the skier starting from $$$4$$$ is $$$4 \rightarrow 2$$$;
• the optimal path for the skier starting from $$$5$$$ is $$$5 \rightarrow 4 \rightarrow 3 \rightarrow 1$$$.

In the second test, $$$h = [3, 2, 2, 1, 1, 1, 0, 0, 0]$$$. The skier starting from $$$1$$$ can ski along at most $$$5$$$ trails, in the path $$$1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 7$$$.

• at the location $$$1$$$, the kinetic energy is $$$0$$$;
• at the location $$$3$$$, the kinetic energy increases by $$$1$$$ (because $$$h_3 < h_1$$$), so it becomes $$$1$$$;
• at the location $$$2$$$, the kinetic energy decreases by $$$1$$$ (because $$$h_2 = h_3$$$), so it becomes $$$0$$$;
• at the location $$$5$$$, the kinetic energy increases by $$$1$$$ (because $$$h_5 < h_2$$$), so it becomes $$$1$$$;
• at the location $$$4$$$, the kinetic energy decreases by $$$1$$$ (because $$$h_4 = h_5$$$), so it becomes $$$0$$$;
• at the location $$$7$$$, the kinetic energy increases by $$$1$$$ (because $$$h_7 < h_4$$$), so it becomes $$$1$$$.

There isn't any sequence of trails of length greater than $$$5$$$ such that the kinetic energy is always non-negative.

In the third test, for the skier starting from vertex $$$1$$$, the optimal path is $$$1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 6 \rightarrow 11 \rightarrow 10 \rightarrow 11$$$.

Here are pictures of the first, second, and third test, with the base lodges shown in red: