409373: GYM103492 K Jumping Monkey
Description
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$$$.
InputThe 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$$$.
OutputFor each test case, output $$$n$$$ lines. The $$$k$$$-th line contains an integer representing the answer when the monkey starts from node $$$k$$$.
ExampleInput2 3 1 2 2 3 1 2 3 5 1 2 1 3 2 4 2 5 1 4 2 5 3Output
3 2 1 4 2 3 1 3Note
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$$$.