LIS on Tree

题目描述

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

我们沿着从顶点 $1$ 到顶点 $k$ 的最短路径，把路径上顶点上的整数按出现的顺序排列成一个序列。求该序列的最长严格递增子序列的长度。

这里，长度为 $L$ 的序列 $A$ 的最长严格递增子序列是下标为 $A_{i_1} , A_{i_2} , ... , A_{i_M}$ 且使得 $M$ 尽可能大的序列，满足 $1 \leq i_1 < i_2 < ... < i_M \leq L$ 且 $A_{i_1} < A_{i_2} < ... < 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$ 的最短路径上得到的序列的最长严格递增子序列的长度。

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$ 到顶点 $5$ 的最短路径得到的序列 $A$ 为 $1,2,5,3,4$。它的最长严格递增子序列是 $A_1, A_2, A_4, A_5$，长度为 $4$.

标签: AtCoder|abc165F

来源

AtCoder|abc165F