题目描述

We have a tree with $N$ vertices, whose $i$-th edge connects Vertex $u_i$ and Vertex $v_i$. Vertex $i$ has an integer $a_i$ written on it. For every integer $k$ from $1$ through $N$, solve the following problem:

• We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex $1$ to Vertex $k$, in the order they appear. Find the length of the longest increasing subsequence of this sequence.

Here, the longest increasing subsequence of a sequence $A$ of length $L$ is the subsequence $A_{i_1} , A_{i_2} , ... , A_{i_M}$ with the greatest possible value of $M$ such that $1 \leq i_1 \lt i_2 \lt ... \lt i_M \leq L$ and $A_{i_1} \lt A_{i_2} \lt ... \lt A_{i_M}$.

我们有一棵有 $N$ 个顶点的树，其 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$ 。顶点 $i$ 上写有一个整数 $a_i$ 。求从 $1$ 到 $N$ 的每一个整数 $k$ 的解：

• 我们将沿着顶点 $1$ 到顶点 $k$ 的最短路径，把写在顶点上的整数按出现的先后顺序排成一个序列。求这个序列中最长的递增子序列的长度。

这里，长度为 $L$ 的序列 $A$ 的最长递增子序列是 $A_{i_1} , A_{i_2} , ... , A_{i_M}$ 的最大可能值 $M$ 的子序列 $A_{i_1} , A_{i_2} , ... , A_{i_M}$ ，即 $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}$ 。

输入格式

输入内容按以下格式标准输入：

$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

样例输入 #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

说明

数据规模与约定

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

样例 $1$ 解释

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