33752번 - LIS on Tree 다국어

문제

You are given a tree of $n$ nodes. Each node has a non-negative integer value $v_i$.

Let a tree subsequence be a sequence of nodes $S = s_1, s_2, \dots s_k$ such that there exists vertices $u, v$ in the tree such that $S$ is a subsequence of the unique shortest path starting at $u$ and ending at $v$.

A tree subsequence is increasing if for all 1ドル \leq i \leq k - 1$ we have that $v_{s_i} < v_{s_{i + 1}}$ (Note that this corresponds to a strictly increasing sequence).

Find the length of the longest increasing tree subsequence.

입력

The first line of input contains a single integer $n$ (1ドル \leq n \leq 3\cdot 10^5$) --- the number of nodes in the tree.

The second line of input contains $n$ integers $v_1, v_2, \cdots, v_n$ (1ドル \leq v \leq 10^{9}$) --- the value of each node in the tree.

The following $n - 1$ lines each contain two integers $a_i, b_i$ (1ドル \leq a_i, b_i \leq n$)--- the endpoints of edge $i$.

It is guaranteed that the given edges form a tree.

출력

Output a single integer --- the length of the longest increasing tree subsequence.

제한

힌트