分数: 600 点
问题陈述
我们有一棵树 N 顶点,其 i第一条边连接顶点 u_i 和顶点 v_i。 顶点 i 有一个整数 上面写着 a_i 。 对于每个整数 k 来自 1 通过 N,解决以下问题:
- 我们将通过沿着从 Vertex 开始的最短路径排列写在顶点上的整数来创建一个序列 1 到顶点 k,按照它们出现的顺序。求该序列的最长递增子序列的长度。
这里,序列的最长递增子序列 A 长度 L 是子序列 A_{i_1} , A_{i_2} , ... , A_{i_M} 的最大可能值为 M 这样 1 \leq i_1 < i_2 < ... < i_M \leq L 和 A_{i_1} < A_{i_2} < ... < A_{i_M}.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq a_i \leq 10^9
- 1 \leq u_i , v_i \leq N
- u_i \neq v_i
- 给定的图是一棵树。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}
输出
打印 N 行。的 k第行,打印从 Vertex 的最短路径获得的序列的最长递增子序列的长度 1 到顶点 k.
示例输入 1
10 1 2 5 3 4 6 7 3 2 4 1 2 2 3 3 4 4 5 3 6 6 7 1 8 8 9 9 10
示例输出 1
1 2 3 3 4 4 5 2 2 3
例如,序列 A 从 Vertex 的最短路径获得 1 到顶点 5 is 1,2,5,3,4。其最长递增子序列为 A_1, A_2, A_4, A_5,长度为 4.