← 返回题目列表

AtCoder · abc165_f

F. 树上的 LIS

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

分数: 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.