题目描述

我们有一棵具有$N$个顶点的树，第$i$条边连接了顶点$u_i$和顶点$v_i$。顶点$i$上有一个整数$a_i$。对于从$1$到$N$的每个整数$k$，解决以下问题：

• 我们将通过按照它们出现的顺序将写在顶点上的整数沿着从顶点$1$到顶点$k$的最短路径排列成一个序列。找到该序列的最长递增子序列的长度。

这里，序列$A$的最长递增子序列是满足$1 \leq i_1 < i_2 < ... < i_M \leq L$和$A_{i_1} < A_{i_2} < ... < A_{i_M}$的子序列$A_{i_1} , A_{i_2} , ... , A_{i_M}$中$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$行，打印出从顶点$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

例如，从顶点$1$到顶点$5$的最短路径得到的序列$A$是$1,2,5,3,4$。其最长递增子序列是$A_1, A_2, A_4, A_5$，长度为$4$。