题目描述

给您一棵 $n$ 个节点的树，树的每个节点上都有一个值 $a_i$。

现在要您求出从 $1$ 号点到 $i$ 号点的路径上最长上升子序列的长度。

输入格式

第一行一个数 $n$，表示节点个数

第二行共 $n$ 个数，第 $i$ 个数表示 $a_i$，含义见题面

接下来共有 $n-1$ 行，第两个数 $u,v$，表示 $u$ 和 $v$ 之间存在一条边

输出格式

输出共包含 $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

提示

• $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$ 到 $i$ 的路径上的最长上升子序列不要求一定以 $i$ 结尾。