CF1654G Snowy Mountain

在一座雪山山脉上有 $n$ 个地点（编号为 $1$ 到 $n$），通过 $n-1$ 条小径连通，整体构成一棵树。每条小径长度为 $1$。其中一些地点是“基地小屋”。每个地点的高度 $h_i$ 定义为该地点到最近的基地小屋的距离（基地小屋的高度为 $0$）。 每个地点上都有一名滑雪者，初始动能为 $0$。每位滑雪者希望沿着尽可能多的小径滑行。假设滑雪者正沿着从地点 $i$ 到地点 $j$ 的小径滑行。滑雪者不允许上坡滑行（即 $h_i < h_j$ 时不可滑行）。如果是平地滑行（即 $h_i = h_j$），则消耗 $1$ 单位动能；如果是下坡滑行（即 $h_i > h_j$），则获得 $1$ 单位动能。对于每个地点，计算从该地点出发，滑雪者在动能始终不为负的前提下，最多能连续滑行的小径数。滑雪者可以多次经过同一地点或小径。

第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）。 第二行包含 $n$ 个整数 $l_1, l_2, \ldots, l_n$（$0 \le l_i \le 1$）。如果 $l_i = 1$，则地点 $i$ 是基地小屋；如果 $l_i = 0$，则地点 $i$ 不是基地小屋。保证至少有一个基地小屋。 接下来的 $n-1$ 行，每行包含两个整数 $u, v$（$1 \leq u, v \leq n$，$u \neq v$），表示有一条小径连接地点 $u$ 和 $v$。保证这些小径构成一棵树。

输出 $n$ 个整数，第 $i$ 个整数表示从地点 $i$ 出发，滑雪者在动能始终不为负的前提下，最多能连续滑行的小径数。

在第一个测试中，$h = [0, 0, 1, 1, 2, 3]$。从 $6$ 号地点出发的滑雪者最多可以滑行 $5$ 条小径，路径为 $6 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 4 \rightarrow 2$（注意滑雪者可以多次经过同一小径或地点）： - 在 $6$ 号地点，动能为 $0$； - 到 $5$ 号地点，下坡，动能增加 $1$（因为 $h_5 < h_6$），变为 $1$； - 到 $4$ 号地点，下坡，动能增加 $1$（因为 $h_4 < h_5$），变为 $2$； - 到 $3$ 号地点，平地，动能减少 $1$（因为 $h_3 = h_4$），变为 $1$； - 回到 $4$ 号地点，平地，动能减少 $1$（因为 $h_4 = h_3$），变为 $0$； - 到 $2$ 号地点，下坡，动能增加 $1$（因为 $h_2 < h_4$），变为 $1$。 不存在任何长度大于 $5$ 的小径序列能保证动能始终不为负。 此外， - 从 $1$ 号地点出发的最优路径为 $1$（不滑行）； - 从 $2$ 号地点出发的最优路径为 $2$（不滑行）； - 从 $3$ 号地点出发的最优路径为 $3 \rightarrow 1$； - 从 $4$ 号地点出发的最优路径为 $4 \rightarrow 2$； - 从 $5$ 号地点出发的最优路径为 $5 \rightarrow 4 \rightarrow 3 \rightarrow 1$。 在第二个测试中，$h = [3, 2, 2, 1, 1, 1, 0, 0, 0]$。从 $1$ 号地点出发的滑雪者最多可以滑行 $5$ 条小径，路径为 $1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 7$。 - 在 $1$ 号地点，动能为 $0$； - 到 $3$ 号地点，下坡，动能增加 $1$（因为 $h_3 < h_1$），变为 $1$； - 到 $2$ 号地点，平地，动能减少 $1$（因为 $h_2 = h_3$），变为 $0$； - 到 $5$ 号地点，下坡，动能增加 $1$（因为 $h_5 < h_2$），变为 $1$； - 到 $4$ 号地点，平地，动能减少 $1$（因为 $h_4 = h_5$），变为 $0$； - 到 $7$ 号地点，下坡，动能增加 $1$（因为 $h_7 < h_4$），变为 $1$。 不存在任何长度大于 $5$ 的小径序列能保证动能始终不为负。 在第三个测试中，从 $1$ 号顶点出发的最优路径为 $1 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 3 \rightarrow 6 \rightarrow 11 \rightarrow 10 \rightarrow 11$。 下图为前三个测试的示意图，红色为基地小屋：  由 ChatGPT 4.1 翻译