树上的 LIS

题目描述

有一棵 $N$ 个顶点的树,第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 另外,顶点 $i$ 上写着整数 $a_i$。 对 $1$ 以上 $N$ 以下的所有整数 $k$,解决下面的问题:

• 将顶点 $1$ 到顶点 $k$ 的最短路径上的顶点所写的整数按距顶点 $1$ 由近到远的顺序排列成的数列,其最长上升子序列的长度是多少?

其中,长度为 $L$ 的数列 $A$ 的最长上升子序列,是指在满足 $1 \leq i_1 \lt i_2 \lt ... \lt i_M \leq L$ 且 $A_{i_1} \lt A_{i_2} \lt ... \lt A_{i_M}$ 的子序列 $A_{i_1}, A_{i_2}, ... , A_{i_M}$ 中 $M$ 最大的一个。

输入格式

输入按以下格式从标准输入给出:

$N$
$a_1$ $a_2$ $...$ $a_N$
$u_1$ $v_1$
$u_2$ $v_2$
$:$
$u_{N-1}$ $v_{N-1}$

输出格式

输出 $N$ 行。第 $k$ 行输出将顶点 $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
2
3
3
4
4
5
2
2
3

例如,将顶点 $1$ 到顶点 $5$ 的最短路径上的顶点所写的整数按距顶点 $1$ 由近到远的顺序排列得到的数列 $A$ 为 $1,2,5,3,4$。这个数列的最长上升子序列是 $A_1$, $A_2$, $A_4$, $A_5$,长度为 $4$。

数据范围

• $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$
• 给出的图是一棵树。
• 输入均为整数。