409373: GYM103492 K Jumping Monkey

There is a tree with $$$n$$$ nodes and $$$n-1$$$ edges that make all nodes connected. Each node $$$i$$$ has a distinct weight $$$a_i$$$. A monkey is jumping on the tree. In one jump, the monkey can jump from node $$$u$$$ to node $$$v$$$ if and only if $$$a_v$$$ is the greatest of all nodes on the shortest path from node $$$u$$$ to node $$$v$$$. The monkey will stop jumping once no more nodes can be reached.

For each integer $$$k \in [1, n]$$$, calculate the maximum number of nodes the monkey can reach if he starts from node $$$k$$$.

The first line of the input contains an integer $$$T$$$ $$$(1 \leq T \leq 10^4)$$$, representing the number of test cases.

The first line of each test case contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, representing the number of nodes.

Each of the following $$$n - 1$$$ lines contains two integers $$$u, v$$$ $$$(1 \leq u, v \leq n)$$$, representing an edge connecting node $$$u$$$ and node $$$v$$$. It is guaranteed that the input will form a tree.

The next line contains $$$n$$$ distinct integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 10^9)$$$, representing the weight of each node.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$8 \times 10^5$$$.

For each test case, output $$$n$$$ lines. The $$$k$$$-th line contains an integer representing the answer when the monkey starts from node $$$k$$$.

2
3
1 2
2 3
1 2 3
5
1 2
1 3
2 4
2 5
1 4 2 5 3

3
2
1
4
2
3
1
3

For the second case of the sample, if the monkey starts from node $$$1$$$, he can reach at most $$$4$$$ nodes in the order of $$$1 \to 3 \to 2 \to 4$$$.