트리 위의 LIS

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

요약

트리에서 x_i번 노드에 값 i를 차례로 기록할 때마다, 두 노드를 잇는 경로의 빈 값이 아닌 원소로 만든 최장 증가 부분 수열 길이의 최댓값을 구합니다.

난이도: 어려움10점 중 9점
유형: 트리, 동적 계획법, 세그먼트 트리, 이분 탐색
정답자: 아직 제출이 없습니다

문제

연습 문제가 너무 많은 대회라서, 이번에는 표준적인 자료 구조 문제를 내기로 했다.

정점이 $n$ 개인 트리가 주어진다. 정점마다 처음에는 값이 비어 있다.

두 정점 $(u, v)$ 사이의 트리 최장 증가 부분 수열(longest increasing tree subsequence)은 다음과 같이 구한다.

$u$ 에서 $v$ 까지 경로 위의 정점들에서 비어 있지 않은 값을 순서대로 적는다. 이렇게 얻은 수열의 최장 증가 부분 수열(LIS)을 구한다.

$^\dagger$ 수열 $a_1, \dots, a_m$ 의 부분 수열 $a_{i_1}, a_{i_2}, \dots, a_{i_k}$ ( $1 \le i_1 < i_2 < \cdots < i_k \le m$ )가 $a_{i_1} < a_{i_2} < \cdots < a_{i_k}$ 를 만족하면 증가 부분 수열이라 한다. 증가 부분 수열 가운데 길이가 가장 긴 것을 최장 증가 부분 수열이라 한다.

$x_1, x_2, \dots, x_n$ 이 갱신으로 주어진다. $i$ 번째 갱신에서는 정점 $x_i$ 에 값 $i$ 를 적는다. 각 갱신 후에, 모든 정점 쌍 $(u, v)$ 에 대한 트리 최장 증가 부분 수열의 길이 중 최댓값을 구한다.

모든 $x_i$ 는 서로 다르다.

입력

첫 줄에 테스트 케이스의 수 $t$ ( $1 \le t \le 10^4$ )가 주어진다.

각 테스트 케이스의 첫 줄에는 정점의 수 $n$ ( $2 \le n \le 5 \cdot 10^5$ )이 주어진다. 다음 $n-1$ 개 줄에는 정점 $u$ 와 $v$ ( $1 \le u, v \le n$ )를 잇는 무방향 간선이 주어진다. 입력으로 주어지는 간선은 트리를 이룬다.

마지막 줄에는 갱신 $x_1, \dots, x_n$ 이 주어진다. 모든 테스트 케이스의 $n$ 의 합은 $5 \cdot 10^5$ 을 넘지 않는다.

출력

각 테스트 케이스마다 $n$ 개의 정수를 공백으로 구분해 한 줄에 출력한다. $i$ 번째 정수는 $i$ 번째 갱신 후의 답이다.

힌트

갱신은 정점 $x_i$ 의 값이 $i$ 라는 뜻이지, 정점 $i$ 의 값이 $x_i$ 라는 뜻이 아니다.

예제1

예제 1

입력

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

예상 출력

1 2 2 2 3
1 2 2 2 2 3 3 3 4 4
1 2 3 3 3 3 4 4 4 4 4 4 5 6 7
1 2