← 返回题目列表

Codeforces · 1654/G

G. 雪山

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

雪山山脉上有 $$$n$$$ 个地点(编号从 $$$1$$$ 到 $$$n$$$),由 $$$n-1$$$ 树形小径连接。每条路径的长度为$$$1$$$。有些地点是基地旅馆。每个位置的高度 $$$h_i$$$ 等于到最近基地小屋的距离(基地小屋的高度为 $$$0$$$)。

每个位置都有一名滑雪者,每个滑雪者都有初始动能$$$0$$$。每个滑雪者都希望沿着尽可能多的滑雪道滑雪。假设滑雪者沿着从位置$$$i$$$到$$$j$$$的路径滑雪。滑雪者不允许滑雪上坡(即,如果 $$$h_i < h_j$$$)。沿着平地滑雪需要消耗一单位动能(即,如果 $$$h_i = h_j$$$),滑雪者通过下坡滑雪可以获得一单位动能(即,如果 $$$h_i > h_j$$$)。对于每个位置,计算从该位置开始的滑雪者可以在其动能永远不会变为负值的情况下滑行的最长路径序列的长度。滑雪者可以多次访问同一地点或路线。

输入

第一行包含一个整数 $$$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$$$ 不是基地小屋。保证至少有 $$$1$$$ 基础小屋。

接下来的 $$$n-1$$$ 行中的每一行都包含两个整数 $$$u, v$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$),这意味着有一条路径连接位置 $$$u$$$ 和 $$$v$$$。保证给定的路径形成一棵树。

输出

打印 $$$n$$$ 整数:第 $$$i$$$ 个整数等于从位置 $$$i$$$ 开始的滑雪者可以滑行且其动能不会变为负值的最长路径序列的长度。

示例

输入 #1

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

输出 #1

0 0 1 1 3 5

输入 #2

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

输出 #2

5 3 2 1 1 1 0 0 0

输入 #3

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

输出 #3

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

输入#4

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

输出#4

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

注意

在第一个测试中,$$$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$$$开始的滑雪者最多可以沿着路径$$$1 \rightarrow 3 \rightarrow 2 \rightarrow 5 \rightarrow 4 \rightarrow 7$$$沿着$$$5$$$路径滑雪。

- 在$$$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$$$。

这是第一次、第二次和第三次测试的图片,其中基地小屋以红色显示: