Problem:


Score : 600 points

Problem Statement

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:

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.

Here, 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}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i \leq 10^9

1 \leq u_i , v_i \leq N

u_i \neq v_i

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

Output

Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

Sample Input 1

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Sample Output 1

1
2
3
3
4
4
5
2
2
3

For 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.



Sample input:
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10


Sample output:
1
2
3
3
4
4
5
2
2
3

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

N = int(input())
A = list(map(int, input().split()))

tree = [[] for i in range(N)]
for i in range(N-1):
  u, v = map(int, input().split())
  tree[u-1].append(v-1); tree[v-1].append(u-1)


ans = [0] * N
ans[0] = 1
dp = [10**10] * N
dp[0] = A[0]
stack = []
def dfs(node, par):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    ans[child] = idx + 1
    stack.append([idx, dp[idx]])
    dp[idx] = num
    dfs(child, node)
    idx, num = stack.pop()
    dp[idx] = num

dfs(0, -1)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
dp = [10**10]*n
for _ in range(n-1):
    u,v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

ans = [None]*n
ans[0] = 1
def dfs(k, p, dp):
    for v in edges[k]:
        if v != p:
            r = bl(dp, a[v])
            x = dp[:]
            x[r] = a[v]
            ans[v] = n - x.count(10**10) + 1
            dfs(v, k, x)
    return 
dfs(0, -1, dp)
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

import sys
input = sys.stdin.readline

n = int(input())
al = list(map(int,input().split()))

from collections import defaultdict
G = defaultdict(list)

for _ in range(n-1):
    u,v = map(int,input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [float("inf") for _ in range(n+1)]
dp[0] = -1
used = [0 for i in range(n)]
used[0] = 1


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    for i in range(n):
        if dp[i] == float("inf"):
            ansl[pos] = i - 1
            break
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


dfs(0)
flag = False
for i in range(n):
    print(ansl[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    begin = [-1] * n
    end = [-1] * n
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        end[pos] = len(res)
        if begin[pos] == -1:
            begin[pos] = len(res) - 1
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res, begin, end


n = int(input())
a = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

dp = []
res, _, _ = eular_tour(tree, 0)

array_ind = [0]
array_val = [a[0]]
lis_array = [1]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack = []
for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        array_val.append(val)
        if val > lis_array[-1]:
             lis_array.append(val)
             stack.append((-1, -1))
        else:
            pos = bisect_left(lis_array, val)
            stack.append((pos, lis_array[pos]))
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        del array_val[-1]
        pos, val = stack.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

A = [0] + list(map(int, input().split()))
G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1
#print(AA, a2f)

R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
ss.update(AA[1], 1)
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            stack += [-u, u]
    else:
        ss.update(AA[-v], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Wrong Answer

Solution code:
from collections import deque


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    begin = [-1] * n
    end = [-1] * n
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        end[pos] = len(res)
        if begin[pos] == -1:
            begin[pos] = len(res) - 1
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res, begin, end


n = int(input())
a = list(map(int, input().split()))
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

dp = []
res, _, _ = eular_tour(tree, 0)

array_ind = [0]
array_val = [a[0]]
lis_array = [1]
ans = [0] * n
ans[0] = 1

for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        array_val.append(val)
        max_ = 1
        for i in range(len(lis_array)):
             if array_val[i] < val:
                 max_ = max(max_, lis_array[i] + 1)
        lis_array.append(max_)
        ans[ind] = max_
    else:
        del array_ind[-1]
        del array_val[-1]
        del lis_array[-1]

for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
aa = {}
j = 0
for i in [int(i) for i in input().split()]:
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
    j += 1
a = [0] * n
k = 1
for i in sorted(list(aa)):
    for j in aa[i]:
        a[j] = k
    k += 1

class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([-1] * (max(a)+10), max, -1)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1, x=[]):
    if r == -1:
        pass
    else:
        y = seg.get_segment(0, a[i])
        if y == -1:
            ans1[i] = 1
        else:
            if y >= len(x):
                exit()
            ans1[i] = ans1[x[y]] + 1
        ans2[i] = max(ans1[r], ans1[i])

    be = seg.b[a[i]]
    seg.update_func(a[i], len(x))
    x.append(i)
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i, x)
    x.pop()
    seg.update(a[i], be)


dfs()
for i in ans2:
    print(i)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from copy import deepcopy
import sys
sys.setrecursionlimit(10 ** 9)
 
n = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(n)]
for i in range(n-1):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  to[u].append(v)
  to[v].append(u)
u = []
ans = [0] * n
# print(to)
# exit()
def dfs(v, l, before=-1):
  # print(v)
  global u, to, a, ans
  for next_v in to[v]:
    if next_v == before:
      continue
    if len(l) == 0:
      l.append(a[next_v])
      # u.append(next_v)
    elif a[next_v] > l[-1]:
      # Lの末尾よりaが大きければ増加部分列を延長できる
      l.append(a[next_v])
      # u.append(next_v)
    else:
      # そうでなければ、「aより小さい最大要素の次」をaにする
      # 該当位置は、二分探索で特定できる
      l[bisect_left(l, a[next_v])] = a[next_v]
    ans[next_v] = len(l)
    dfs(next_v, deepcopy(l),  v)
    # if len(u) > 0 and u[-1] == next_v:
    #   l.pop(); u.pop()
    
dfs(0, [])
for i in range(n):
  print(ans[i]+1)

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


class TreeConstructor:
    def __init__(self, uv):
        self.table = defaultdict(list)
        for u, v in uv:
            self.table[u].append(v)
            self.table[v].append(u)

    def view(self, root_index):
        children_table = dict()
        parent_table = dict()
        checked = {root_index}
        q = [root_index]
        while len(q) != 0:
            current = q.pop()
            next_nodes = [a for a in self.table[current] if a not in checked]
            for a in next_nodes:
                checked.add(a)
                parent_table[a] = current
            if len(next_nodes) != 0:
                children_table[current] = next_nodes
                q.extend(next_nodes)
        return children_table, parent_table


def main():
    # f([3, 5, 2, 4, 6])
    N = int(input())
    A = [int(a) for a in input().split()]
    uv = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    uv = [
        sorted(a) for a in uv
    ]
    children_table, parent_table = TreeConstructor(uv).view(1)

    result = dict()
    result[1] = [1]

    def f(path):
        if path[-1] in result:
            return
        f(path[:-1])

        DP = result[path[-2]]

        maxindex = len(DP) - 1

        ind = path[-1]
        elem = A[ind - 1]
        for j in range(maxindex, -1, -1):
            if DP[j] < elem:
                if len(DP) == j + 1:
                    result[ind] = DP + [elem]
                    return
                if elem < DP[j + 1]:
                    DDD = [a for a in DP]
                    DDD[j + 1] = elem
                    result[ind] = DDD
                    return
        result[ind] = [a for a in DP]

    def get_path(index):
        if index == 1:
            return [1]
        return get_path(parent_table[index]) + [index]

    for i in range(1, N + 1):
        if i in children_table:
            continue
        p = get_path(i)
        f(p)
    for i in range(N):
        print(len(result[i + 1] or []))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
aa = {}
j = 0
for i in [int(i) for i in input().split()]:
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
    j += 1
a = [0] * n
k = 1
for i in sorted(list(aa)):
    for j in aa[i]:
        a[j] = k
    k += 1
exit()

class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([-1] * (max(a)+10), max, -1)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1, x=[]):
    if r == -1:
        pass
    else:
        y = seg.get_segment(0, a[i])
        if y == -1:
            ans1[i] = 1
        else:
            ans1[i] = ans1[x[y]] + 1
        ans2[i] = max(ans1[r], ans1[i])

    be = seg.b[a[i]]
    seg.update_func(a[i], len(x))
    x.append(i)
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i, x)
    x.pop()
    seg.update(a[i], be)


dfs()
for i in ans2:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def dijkstra(n, graph, s):
    """
    n: number of nodes (Int)
    graph: weithted graph (List[List[(node(Int), weight(Int))]])
    s: source node (Int)
    """
    dist = [float('inf')] * n # distance from source
    hq = [(0, s, 0)] # (distance_from_source, current_node, length_of_current_increasing_sequence)
    dist[s] = 0
    ans = [0] * n # length_of_lis
    ans[0] = 1
    while hq:
        d, v, cur = heappop(hq)
        if dist[v] < d:
            continue
        for w, cost in graph[v]:
            if dist[v] + cost <= dist[w]:
                dist[w] = dist[v] + cost
                ans[w] = ans[v]
                if A[w] > A[v]:
                    ans[w] = max(ans[w], cur+1) 
                    heappush(hq, (dist[w], w, cur+1))
                else:
                    heappush(hq, (dist[w], w, 1))
    return ans

N = int(input())
A = tuple(map(int, input().rstrip().split()))
graph = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    graph[u].append((v, 1))
    graph[v].append((u, 1))
ans = dijkstra(N, graph, 0)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 9)
 
n = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(n)]
for i in range(n-1):
  u, v = map(int, input().split())
  u -= 1; v -= 1
  to[u].append(v)
  to[v].append(u)
l = []
u = []
ans = [0 for _ in range(n)]
# print(to)
# exit()
def dfs(v, before=-1):
  # print(v)
  global l,u, to, a, ans
  for next_v in to[v]:
    if next_v == before:
      continue
    if len(l) == 0:
      l.append(a[next_v])
      u.append(next_v)
    elif a[next_v] > l[-1]:
      # Lの末尾よりaが大きければ増加部分列を延長できる
      l.append(a[next_v])
      u.append(next_v)
    else:
      # そうでなければ、「aより小さい最大要素の次」をaにする
      # 該当位置は、二分探索で特定できる
      l[bisect_left(l, a[next_v])] = a[next_v]
    ans[next_v] = len(l)
    dfs(next_v, v)
    if len(u) > 0 and u[-1] == next_v:
      l.pop(); u.pop()
    
dfs(0)
for i in range(n):
  print(ans[i]+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def dijkstra(n, graph, s):
    """
    n: number of nodes (Int)
    graph: weithted graph (List[List[(node(Int), weight(Int))]])
    s: source node (Int)
    """
    dist = [float('inf')] * n # distance from source
    hq = [(0, s, 0)] # (distance_from_source, current_node, length_of_current_increasing_sequence)
    dist[s] = 0
    ans = [0] * n # length_of_lis
    ans[0] = 1
    while hq:
        d, v, cur = heappop(hq)
        if dist[v] < d:
            continue
        for w, cost in graph[v]:
            if dist[v] + cost <= dist[w]:
                dist[w] = dist[v] + cost
                ans[w] = ans[v]
                if A[w] > A[v]:
                    ans[w] += 1
                    heappush(hq, (dist[w], w, cur+1))
                else:
                    heappush(hq, (dist[w], w, 1))
    return ans

N = int(input())
A = tuple(map(int, input().rstrip().split()))
graph = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    graph[u].append((v, 1))
    graph[v].append((u, 1))
ans = dijkstra(N, graph, 0)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

#ライブラリインポート
from collections import defaultdict
import bisect
INF = float("inf")

#入力受け取り
def getlist():
	return list(map(int, input().split()))


class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def Euler_tour(G, node, visit, DP, prev, ans, A):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			#LIS更新
			x = bisect.bisect_left(DP, A[i])
			prev[x] = DP[x]
			DP[x] = A[i]
			ans[i] = bisect.bisect_left(DP, INF)
			# print(DP, i)
			# print(prev)
			Euler_tour(G, i, visit, DP, prev, ans, A)

	#LIS戻す
	x = bisect.bisect_left(DP, A[node] + 1) - 1
	DP[x] = prev[x]
	prev[x] = INF

#処理内容
def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS初期化
	DP = [INF] * N
	DP[0] = A[0]
	prev = [INF] * N
	ans = [None] * N
	ans[0] = 1
	visit = ["No"] * N
	visit[0] = "Yes"
	Euler_tour(G, 0, visit, DP, prev, ans, A)
	for i in range(N):
		print(ans[i])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left


def solve(n, a_list, uv_list):
    res = [0] * n
    tree = [[] for _ in range(n)]
    for u, v in uv_list:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    # euler tour
    visited = [0] * n
    parent = [-1] * n
    tour = [0]
    p = 0
    while True:
        visited[p] = 1
        r = parent[p]
        while len(tree[p]):
            q = tree[p].pop()
            if visited[q] == 0:
                parent[q] = p
                r = q
                break
        if r == -1:
            break
        p = r
        tour.append(p)
    assert len(tour) == 2 * n - 1

    # tree DP
    dp = [10 ** 9 + i for i in range(n + 1)]
    dp[0] = 0
    re_visited = [0] * n
    callbacks = []
    for p in tour:
        if re_visited[p] == 0:
            re_visited[p] = 1
            ind = bisect_left(dp, a_list[p])
            callbacks.append((ind, dp[ind]))
            dp[ind] = a_list[p]
            res[p] = ind
        else:
            ind, v = callbacks.pop()
            dp[ind] = v
        # print(dp)

    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    uv_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, a_list, uv_list)
    for r in res:
        print(r)


def test():
    assert solve(10, [1, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [3, 4], [4, 5], [3, 6], [6, 7], [1, 8], [8, 9], [9, 10]]
                 ) == [1, 2, 3, 3, 4, 4, 5, 2, 2, 3]
    assert solve(10, [5, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10]]
                 ) == [1, 1, 1, 1, 1, 2, 2, 1, 1, 1]
    assert solve(10, [5, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 1, 2, 2, 2, 2, 2, 2, 1, 2]
    assert solve(10, [3, 5, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 2, 2, 1, 2, 3, 3, 1, 1, 2]
    assert solve(10, [3, 3, 3, 3, 3, 3, 3, 3, 3, 3],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]


if __name__ == "__main__":
    test()
    main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

#ライブラリインポート
from collections import defaultdict
import bisect
INF = float("inf")

#入力受け取り
def getlist():
	return list(map(int, input().split()))


class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def Euler_tour(G, node, visit, DP, prev, ans, A):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			#LIS更新
			x = bisect.bisect_left(DP, A[i])
			prev[x] = DP[x]
			DP[x] = A[i]
			ans[i] = bisect.bisect_left(DP, INF)
			# print(DP, i)
			# print(prev)
			Euler_tour(G, i, visit, DP, prev, ans, A)

	#LIS戻す
	x = bisect.bisect_left(DP, A[node] + 1) - 1
	DP[x] = prev[x]
	prev[x] = INF

#処理内容
def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS初期化
	DP = [INF] * N
	DP[0] = 1
	prev = [INF] * N
	ans = [None] * N
	ans[0] = 1
	visit = ["No"] * N
	visit[0] = "Yes"
	Euler_tour(G, 0, visit, DP, prev, ans, A)
	for i in range(N):
		print(ans[i])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

#ライブラリインポート
from collections import defaultdict
import bisect
INF = float("inf")

#入力受け取り
def getlist():
	return list(map(int, input().split()))


class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def Euler_tour(G, node, visit, DP, prev, ans, A):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			#LIS更新
			x = bisect.bisect_left(DP, A[i])
			prev[x] = DP[x]
			ans[i] = x + 1
			DP[x] = A[i]
			# print(DP)
			# print(prev)
			Euler_tour(G, i, visit, DP, prev, ans, A)

	#LIS戻す
	x = bisect.bisect_left(DP, A[node] + 1) - 1
	DP[x] = prev[x]


#処理内容
def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS初期化
	DP = [INF] * N
	DP[0] = 1
	prev = [INF] * N
	ans = [None] * N
	ans[0] = 1
	visit = ["No"] * N
	visit[0] = "Yes"
	Euler_tour(G, 0, visit, DP, prev, ans, A)
	for i in range(N):
		print(ans[i])


if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
a = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)

ans = [0] * n
ans[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1, x=[], y=[]):
    if r == -1:
        x.append(a[i])
    else:
        if x[0] >= a[i]:
            ans[i] = 1
        else:
            mi = 0
            ma = len(x) - 1
            while mi != ma:
                mm = (mi + ma) // 2+1
                if x[mm] < a[i]:
                    mi = mm
                else:
                    ma = mm - 1
            ans[i] = ans[y[mi]]+1
        ans2[i] = max(ans2[r], ans[i])
        x.append(max(x[-1], a[i]))
    y.append(i)
    for j in e[i]:
        if j != r:
            dfs(j, i)
    y.pop()
    x.pop()


dfs()
for i in ans2:
    print(i)

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

A = [0] + list(map(int, input().split()))
G = [[] for _ in range(N+1)]
for v in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1
#print(AA, a2f)

R = [0]*(N+1)
R[1] = 1
ss = SegTree([1]*(N+1), N+1, -1, max)
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        parent = path[-1]
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[i])