LIS on Tree#10657
We have a tree with vertices, whose -th edge connects Vertex u_i and Vertex v_i. Vertex has an integer a_i written on it. For every integer from through , solve the following problem:
We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex to Vertex , in the order they appear. Find the length of the longest increasing subsequence of this sequence.
Here, the longest increasing subsequence of a sequence of length is the subsequence A_{i_1}, A_{i_2}, \ldots, A_{i_m} with the greatest possible value of such that 1 \leq i_1 < i_2 < \ldots < i_m \leq L and A_{i_1} < A_{i_2} < \ldots < A_{i_m}.
The first line contains number (2 \leq n \leq 2 \cdot 10^5). The second line contains numbers a_1, a_2, \ldots, a_n (1 \leq a_i \leq 10^9). Each of the next n - 1 lines contains an edge (u_i, v_i) (1 \leq u_i, v_i \leq n).
Print lines. In the -th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex to Vertex .
Example 1