LIS On Tree

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.

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.