406818: GYM102565 G Puppetteer

You are given a rooted tree with $$$N$$$ nodes, each node containing a distinct integer value $$$p_i$$$ from the interval $$$[1,N]$$$. The root of the tree is vertex $$$1$$$.

An interval $$$[a,b]$$$ is called compact for a set $$$S$$$ if all integers from $$$a$$$ to $$$b$$$ are present in $$$S$$$, but $$$a-1$$$ and $$$b+1$$$ are not present in $$$S$$$.

For each vertex, find the number of compact intervals formed by the values in its subtree (including that vertex).

The first line of the input contains a number $$$1 \leq T \leq 10^{18}$$$, the number of tests.

For each test, the first line contains an integer $$$1 \leq N \leq 250.000$$$, the number of vertices in the tree.

The next line contains $$$N$$$ numbers $$$1 \leq p_i \leq N$$$, representing the values for each vertex from $$$1$$$ to $$$N$$$. All values $$$p_i$$$ are pairwise distinct.

The following $$$N-1$$$ lines will each contain a pair of integers ($$$a, b$$$) signifying that there is an edge between node $$$a$$$ and node $$$b$$$ ($$$1 \leq a, b \leq N$$$).

It is guaranteed that the sum of all $$$N$$$ is less than $$$500.000$$$.

The output should contain $$$T$$$ lines, containing the answer for each test, the line $$$i$$$ having $$$N_i$$$ numbers, representing the number of compact intervals in the subtree of each vertex from $$$1$$$ to $$$N_i$$$.

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

1 3 2 1 1 3 1 2 
1 1 2 1 1 1 2