AT_abc165_f [ABC165F] LIS on Tree

题目描述

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

输入格式

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

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

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

输出格式

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

输入输出样例 #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\le n\le 2e5,a_i\le 1e9, u\le n,v\le n,u\neq v$