409380: GYM103495 F Jumping Monkey II
Description
There is a tree with $$$n$$$ nodes and $$$n-1$$$ edges that make all nodes connected. Each node $$$i$$$ has a weight $$$a_i$$$. A monkey is jumping on the tree. In each jump, he can go from one node to another through an edge. If the monkey starts from node $$$u_1$$$, passes through $$$u_2,u_3,\dots,u_{k-1}$$$, and ends in $$$u_k$$$, where all visited nodes are distinct, we call $$$u_1,u_2,u_3,\dots,u_k$$$ a simple path. Let's define the LIS (Longest Increasing Subsequence) of a simple path $$$u_1,u_2,u_3,\dots,u_k$$$ as follow:
- The longest sequence $$$p_1,p_2,\dots,p_l$$$ that meets $$$1 = p_1 < p_2 < \dots < p_l \le k$$$ and $$$a_{u_{p_1}}<a_{u_{p_2}}<\dots<a_{u_{p_l}}$$$.
The monkey wants to make the LIS as long as possible. For each $$$i \in [1, n]$$$, please calculate the maximum length of the LIS he can get if he starts from node $$$i$$$.
InputThe first line of the input contains an integer $$$T$$$ ($$$1 \leq T \leq 10^4$$$), indicating the number of test cases.
The first line of each test case contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \times 10^5$$$), indicating the number of nodes.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), indicating the weight of each node.
Each of the following $$$n - 1$$$ lines contains two integers $$$u, v$$$ ($$$1 \leq u, v \leq n$$$), indicating an edge connecting nodes $$$u$$$ and $$$v$$$. It is guaranteed that the given edges form a tree.
It is guaranteed that $$$\sum n \leq 2 \times 10^5$$$ over all test cases.
OutputFor each test case, output $$$n$$$ lines, the $$$i$$$-th of which is the maximum length of the LIS the monkey can get if he starts from node $$$i$$$.
ExampleInput2 5 1 2 3 4 5 1 2 1 3 2 4 2 5 5 3 2 5 4 1 1 2 2 3 3 4 4 5Output
3 2 2 2 1 2 2 1 2 3