最长上升子树列
说明
传统的最长上升子序列（LIS）问题，最优的解法复杂度是$O(n \log n)$的。然而这个问题太简单了！我们来加大一点难度。给定一颗 $n$ 个点的有根树，根结点为 $1$ 。树上每个点都有一个点权。
这样以来，从点 $1$ 到达每个结点，都经过一个唯一路径。这些路径上的点恰好可以构成一个序列。
现在请你求出，从点 $1$ 分别到达 $1,2,...,n$ 的路径上，最长上升子序列（严格）的长度分别各是多少？
输入格式
输入共 $n+1$ 行。输入第一行，一个整数 $n$ ($2\leq n\leq 2\times10^5$)
输入第二行，$n$ 个整数 $a_i$ ,代表每个点的点权。($1\leq a_i \leq 10^9$)
接下来 $n-1$ 行，每行 $2$ 个整数 $x,y$ 。代表 $x,y$ 在树上有一条连边。 ($1\leq x,y \leq n$)
输出格式
输出 $n$ 行，每行一个整数，第 $i$ 行代表从 $1$ 号结点到 $i$ 号结点路径上的最长上升子序列的长度。样例
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