题目描述

$N$ 頂点の木があり、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結んでいます。 また、頂点 $i$ には整数 $a_i$ が書かれています。 $1$ 以上 $N$ 以下のすべての整数 $k$ に対して、次の問題を解いてください。

• 頂点 $1$ から頂点 $k$ までの最短パス上の頂点に書かれている整数を頂点 $1$ に近い方から順に並べた数列の最長増加部分列の長さはいくつか。

なお、長さ $L$ の数列 $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$ が大きいものをいいます。

输入格式

入力は以下の形式で標準入力から与えられる。

$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$ に近い方から順に並べた数列の最長増加部分列の長さを出力せよ。

题目大意

给您一棵$n$个节点的树，树的每个节点上都有一个值$a_i$。现在要您求出从$1$号点到$i$号点的路径上最长上升子序列的长度。

输入格式

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

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

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

输出格式

输出共包含$n$行，每行只有一个数，第$i$行的数表示从$1$号点到$i$号点的路径上最长上升子序列的长度。

数据范围：

$2\le n\le 2e5,a_i\le 1e9, u\le n,v\le n,u\neq v$

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$
• 与えられるグラフは木である。
• 入力はすべて整数である。

Sample Explanation 1

例えば、頂点 $1$ から頂点 $5$ までの最短パス上の頂点に書かれている整数を頂点 $1$ に近い方から順に並べた数列 $A$ は $1,2,5,3,4$ です。この数列の最長増加部分列は $A_1$ , $A_2$ , $A_4$ , $A_5$ であり、この長さは $4$ です。