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 starts with a blank value.

The longest increasing tree subsequence between two nodes $(u, v)$ is computed as follows:

• Write down all the nonblank values on the path from $u$ to $v$, in order. Compute the longest increasing subsequence (LIS) of the resulting sequence.

$^\dagger$ A subsequence $a_{i_1}, a_{i_2}, \dots, a_{i_k}$ with $1 \le i_1 < i_2 < \cdots < i_k \le m$ is increasing if $a_{i_1} < a_{i_2} < \cdots < a_{i_k}$. A longest increasing subsequence is one with the maximum length among all increasing subsequences.

You are given $n$ updates $x_1, x_2, \dots, x_n$. Update $i$ writes the value $i$ at node $x_i$. After each update, compute the maximum longest increasing tree subsequence length over all pairs of nodes $(u, v)$.

All $x_i$ are distinct.

The first line contains the number of test cases $t$ ($1 \le t \le 10^4$).

Each test case starts with one integer $n$ ($2 \le n \le 5 \cdot 10^5$). The next $n-1$ lines each contain two integers $u$ and $v$ ($1 \le u, v \le n$), an undirected edge between nodes $u$ and $v$. The edges form a tree.

The last line of the test case contains the updates $x_1, \dots, x_n$. The sum of $n$ over all test cases does not exceed $5 \cdot 10^5$.

For each test case, print $n$ space-separated integers on a single line. The $i$-th integer is the answer after the $i$-th update.

An update tells you the value of node $x_i$, not that the value of node $i$ is $x_i$.