32747번 - LIS On Tree 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 1024 MB | 10 | 4 | 4 | 44.444% |
문제
There were too many constructive problems in this contest, so we decided to set a standard data structure problem.
You are given a tree with $n$ labeled nodes. Each node also has a blank value initially.
The longest increasing tree subsequence between two nodes $(u, v)$ on the tree is computed as follows:
- Write down all the nonblank values from the nodes on the path from $u$ to $v$, in order. Compute the longest increasing subsequence$^\dagger$ of the resulting sequence.
You are given $n$ updates, $x_1, x_2 \dots x_n$. For update $i$, fill in the value $i$ at node $x_i$. After each update, compute the length of the longest longest increasing tree subsequence among all pairs of nodes $(u, v)$ in the tree.
It is guaranteed that all $x_i$ values are distinct.
$^\dagger$ Define a sequence of integers $a_i...a_m$. A subsequence $a_{i_1}, a_{i_2}, ..., a_{i_k}$ where $1 \leq i_1 < i_2 < \cdots < i_k \leq m$ is called increasing if $a_{i_1} < a_{i_2} < a_{i_3} < ... < a_{i_k}$. An increasing subsequence is called longest if it has maximum length among all increasing subsequences.
입력
The first line of the input contains an integer $1 \leq t \leq 10^4$, denoting the number of test cases.
The first line of each test case contains one integer $2 \leq n \leq 5 \cdot 10^5$.
The next $n - 1$ lines contain two integers $1 \leq u, v \leq n$, denoting an undirected edge between the nodes with labels $u$ and $v$, respectively. It is guaranteed that the input edges form a tree.
The last line of input for the testcase consists of $n$ integers $x_1...x_n$, denoting the updates in order. It is guaranteed that all $x_i$ values are distinct.
It is guaranteed that the sum of $n$ across all test cases does not exceed $5 \cdot 10^5$.
출력
For each test case, print $n$ space-separated integers on a single line, denoting the answer after the $i^\textrm{th}$ update.
예제 입력 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
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
힌트
Remember that the updates tell you the value of the $x_i^\textrm{th$ node}, not that the value of node $i$ is $x_i$.
An example of the process for the first tree is shown below. The yellow nodes are one potential longest increasing tree subsequence after each operation. The node's labels are 1-5 from left to right, initially with blank values.