LIS on Tree

시간 제한4초메모리 제한2048 MB

요약

각 노드에 값이 있는 트리가 주어질 때, 어떤 단순 경로를 따라 나타나는 노드들의 값이 순서대로 엄격히 증가하는 가장 긴 부분수열을 찾는다. 그 길이를 출력한다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, DFS, 이분 탐색
정답자: 아직 제출이 없습니다

문제

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.

예제3

예제 1
입력
```
4
7 7 7 7
2 4
2 3
1 2
```
예상 출력
```
1
```
예제 2
입력
```
5
3 9 14 7 12
1 4
3 4
4 5
2 3
```
예상 출력
```
3
```

예제 3

입력

12
10 3 8 13 6 2 3 14 1 5 10 6
1 10
2 6
2 10
7 9
2 9
9 11
3 7
2 8
5 7
4 7
2 12

예상 출력