{"problem":{"name":"LIS on Tree","description":{"content":"We have a tree with $N$ vertices, whose $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$. Vertex $i$ has an integer $a_i$ written on it. For every integer $k$ from $1$ through $N$, solve the follow","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc165_f"},"statements":[{"statement_type":"Markdown","content":"We have a tree with $N$ vertices, whose $i$\\-th edge connects Vertex $u_i$ and Vertex $v_i$. Vertex $i$ has an integer $a_i$ written on it. For every integer $k$ from $1$ through $N$, solve the following problem:\n\n*   We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex $1$ to Vertex $k$, in the order they appear. Find the length of the longest increasing subsequence of this sequence.\n\nHere, the longest increasing subsequence of a sequence $A$ of length $L$ is the subsequence $A_{i_1} , A_{i_2} , ... , A_{i_M}$ with the greatest possible value of $M$ such that $1 \\leq i_1 < i_2 < ... < i_M \\leq L$ and $A_{i_1} < A_{i_2} < ... < A_{i_M}$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq a_i \\leq 10^9$\n*   $1 \\leq u_i , v_i \\leq N$\n*   $u_i \\neq v_i$\n*   The given graph is a tree.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$\n$a_1$ $a_2$ $...$ $a_N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$:$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc165_f","tags":[],"sample_group":[["10\n1 2 5 3 4 6 7 3 2 4\n1 2\n2 3\n3 4\n4 5\n3 6\n6 7\n1 8\n8 9\n9 10","1\n2\n3\n3\n4\n4\n5\n2\n2\n3\n\nFor example, the sequence $A$ obtained from the shortest path from Vertex $1$ to Vertex $5$ is $1,2,5,3,4$. Its longest increasing subsequence is $A_1, A_2, A_4, A_5$, with the length of $4$."]],"created_at":"2026-03-03 11:01:13"}}