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: Runtime Error

Solution code:
import sys
import bisect

def dfs(u,k,r=0):

    B = [A[u]]
    if u == k:
        return B, True

    for v in E[u]:
        if v == r: continue  # 親は無視

        Ap, has_k = dfs(v,k,u)
        if has_k:
            B.extend(Ap)
            return B, True

    return [], False

def lis(A):
    
    dp = [A[0]]

    if len(A) == 1:
        return 1

    for i in range(len(A)):
        if A[i] > dp[-1]:
            dp.append(A[i])
        else:
            tmp = bisect.bisect_left(dp, A[i])
            dp[bisect.bisect_left(dp, A[i])] = A[i]
    
    return len(dp)

if __name__ == "__main__":

    N = int(sys.stdin.readline())
    A = [int(x) for x in sys.stdin.readline().split()]
    E = [[] for _ in range(N)]  # 辺の情報
    for _ in range(N-1):
        u, v = map(int, sys.stdin.readline().split())
        E[u-1].append(v-1)
        E[v-1].append(u-1)

    for i in range(N):
        C, _ = dfs(0,i)
        print(lis(C))

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

# MOD = 10 ** 9 + 7
MOD = 998244353


def dfs(node, arr):
    # print(node, arr)
    new_arr = arr.copy()
    idx = bisect.bisect_left(arr, num[node])
    lis[node] = idx+1
    if idx < len(arr):
        new_arr[idx] = num[node]
    else:
        new_arr.append(num[node])

    for ne in graph[node]:
        if lis[ne] == -1:
            dfs(ne, new_arr)


n = int(input())
num = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for _ in range(n)]

for e in Edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

lis = [-1]*n
dfs(0, [])

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

Submission status: Runtime Error

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    a = LI()
    uv = [LI_() for _ in range(n-1)]

    e = collections.defaultdict(set)
    for u,v in uv:
        e[u].add(v)
        e[v].add(u)

    seg = Seg(n, 0, max)

    rr = [0] * n
    def f(i, p):
        ai = a[i]
        t = seg.query(0, ai)
        rr[i] = t + 1
        seg.update(ai, t+1)
        for c in e[i]:
            if c == p:
                continue
            f(c, i)
        seg.update(ai, 0)

    f(0, -1)

    return JA(rr, "\n")

print(main())

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000)
import bisect
 
N = int(input())
A = list(map(int,input().split()))
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)
 
INF = 10**15
dp = [ INF for _ in range(N)]
dp[0] = -INF
ans = [None]*(N)
 
def dfs(v, p=-1):
  i = bisect.bisect_left(dp, A[v])
  old = dp[i]
  dp[i] = A[v]
  ans[v] = i
  if p!=-1: ans[v] = max(ans[v], ans[p])
 
  for u in adj[v]:
    if u == p: continue
    dfs(u, v)
 
  dp[i] = old
 
dfs(0)
for i in range(N):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.recursionlimit(100000)
import bisect

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

INF = 10**15
dp = [ INF for _ in range(N)]
dp[0] = -INF
ans = [None]*(N)

def dfs(v, p=-1):
  i = bisect.bisect_left(dp, A[v])
  old = dp[i]
  dp[i] = A[v]
  ans[v] = i
  if p!=-1: ans[v] = max(ans[v], ans[p])

  for u in adj[v]:
    if u == p: continue
    dfs(u, v)

  dp[i] = old

dfs(0)
for i in range(N):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.recursionlimit(10000000)
import bisect

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

INF = 10**15
dp = [ INF for _ in range(N)]
dp[0] = -INF
ans = [None]*(N)

def dfs(v, p=-1):
  i = bisect.bisect_left(dp, A[v])
  old = dp[i]
  dp[i] = A[v]
  ans[v] = i
  if p!=-1: ans[v] = max(ans[v], ans[p])

  for u in adj[v]:
    if u == p: continue
    dfs(u, v)

  dp[i] = old

dfs(0)
for i in range(N):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import bisect

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

INF = 10**15
dp = [ INF for _ in range(N)]
dp[0] = -INF
ans = [None]*(N)

def dfs(v, p=-1):
  i = bisect.bisect_left(dp, A[v])
  old = dp[i]
  dp[i] = A[v]
  ans[v] = i
  if p!=-1: ans[v] = max(ans[v], ans[p])

  for u in adj[v]:
    if u == p: continue
    dfs(u, v)

  dp[i] = old

dfs(0)
for i in range(N):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1e6)
def dfs(vertex):
  visited[vertex] = True
  if vertex != 0:
    maxlen = 0
    x = a[vertex]
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  ans[vertex] = max(L for (L, _) in table)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  table.pop()
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
table = [(1, a[0])]
dfs(0)
[print(value) for value in ans]

Submission status: Runtime Error

Solution code:
def dfs(vertex):
  visited[vertex] = True
  if vertex != 0:
    maxlen = 0
    x = a[vertex]
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  ans[vertex] = max(L for (L, _) in table)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  table.pop()
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
table = [(1, a[0])]
dfs(0)
[print(value) for value in ans]

Submission status: Runtime Error

Solution code:
def longest_subsequence(sequence):
  return 5

def true_longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def dfs(vertex):
  visited[vertex] = True
  node_sequence.append(a[vertex])
  ans[vertex] = longest_subsequence(node_sequence)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  node_sequence.pop()
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
node_sequence = list()
visited = [False]*n
ans = [0]*n
dfs(0)
[print(value) for value in ans]

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    input = sys.stdin.readline
    from collections import deque
    from bisect import bisect_left

    N = int(input())
    a = list(map(int, input().split()))
    tree = [[] for _ in [0]*N]
    for u, v in [map(int, input().split()) for _ in [0]*(N-1)]:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)
    
    dp = [1001001001] * N
    dp[0] = -1001001001
    ans = [0] * N
    def dfs(now, p=-1):
        idx = bisect_left(dp, a[now])
        old = dp[idx]
        dp[idx] = a[now]
        ans[now] = idx
        if p != -1 and ans[now] < ans[p]:
            ans[now] = ans[p]
        for child in tree[now]:
            if child == p: continue
            dfs(child, now)
        dp[idx] = old
    dfs(0)
    
    print(*ans, sep='\n')

main()

Submission status: Runtime Error

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n=int(input())
a=list(map(int,input().split()))
uv=[list(map(int,input().split())) for i in range(n-1)]
edge=defaultdict(list)
for i in range(n-1):
    u,v=uv[i]
    edge[u].append(v)
    edge[v].append(u)
# print(edge)

itta=[0]*(n+1)
# lislist=[0]*(n+1)

def dfs(now,lis):
    stk=0
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
        stk="pop"
    else:
        tmp=bisect.bisect_left(lis, a[now-1])
        stk=[tmp,lis[tmp]]
        lis[tmp]=a[now-1]
    
    # print(now,lis)
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            dfs(i,lis)
    
    if stk=="pop":
        lis.pop()
    else:
        lis[stk[0]]=stk[1]

dfs(1,[float('inf')])

# print(itta)
for i in range(n):
    print(itta[i+1])

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline


def main():
    N = int(input())
    As = list(map(int, input().split()))

    edges = (map(int, readline().strip().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in edges:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 18
    dp = [inf] * (N+1)
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = binary_search(dp, inf)
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while left != right:
        if v <= seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline

sys.setrecursionlimit(10**6)


def main():
    N = int(input())
    As = list(map(int, input().split()))

    query = (map(int, readline().strip().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in query:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 9 + 7
    dp = [inf] * N
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = dp.index(inf)
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while left != right:
        if v <= seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def main():
    N = int(input())
    As = list(map(int, input().split()))

    query = (map(int, input().split()) for _ in range(N-1))

    tree = [[] for _ in range(N)]
    for u, v in query:
        tree[u-1].append(v-1)
        tree[v-1].append(u-1)

    inf = 10 ** 9 + 7
    dp = [inf] * N
    ans = [0] * N

    def dfs(node, parent):
        v = As[node]
        lb = binary_search(dp, v)
        old = dp[lb]
        dp[lb] = v
        ans[node] = lb + 1
        for child in tree[node]:
            if child == parent:
                continue
            dfs(child, node)
        dp[lb] = old

    dfs(0, 0)

    for k in range(N):
        print(ans[k])


def binary_search(seq, v):
    left = 0
    right = len(seq) - 1
    center = right // 2

    while center != right:
        if v < seq[center]:
            right = center
        else:
            left = center+1
        center = (right + left) // 2

    return center


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
a = list(map(int, input().split()))
to = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    to[u].append(v)
    to[v].append(u)
del u, v

ans = [-1] * N


def dfs(v, prev_dp):
    dp = [*prev_dp]
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
    else:
        pos = bisect.bisect_left(dp, a[v])
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)


dfs(0, [])


for an in ans:
    print(an)

Submission status: Runtime Error

Solution code:
def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    w_set = set([_[0] for _ in s1])
    w_set = w_set.union([_[0] for _ in s2])
    w_set = list(w_set)
    w_set.sort()
    i1 = 0
    i2 = 0
    ret = []
    for w in w_set:
        while i1 + 1 < len(s1) and s1[i1 + 1][0] <= w:
            i1 += 1
        while i2 + 1 < len(s2) and s2[i2 + 1][0] <= w:
            i2 += 1
        if s1[i1][1] >= s2[i2][1]:
            val = s1[i1][1]
            com = s1[i1][2]
        else:
            val = s2[i2][1]
            com = s2[i2][2]
        if len(ret) >= 1 and ret[-1][1] >= val:
            continue
        ret.append((w, val, com))
    return ret



N = int(input())
A = [int(_) for _ in input().split()]

parent = [0] * (N + 1)
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    parent[v] = u

#print(parent)

ret = [(0, 0, None)] * (N + 1)
ret[0] = [(0, 0, None)]
for i in range(1, N + 1):
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    #print(ret[i])
    print(ret[i][-1][1])

#print(ret)

Submission status: Runtime Error

Solution code:
def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    w_set = set([_[0] for _ in s1])
    w_set = w_set.union([_[0] for _ in s2])
    w_set = list(w_set)
    w_set.sort()
    i1 = 0
    i2 = 0
    ret = []
    for w in w_set:
        while i1 + 1 < len(s1) and s1[i1 + 1][0] <= w:
            i1 += 1
        while i2 + 1 < len(s2) and s2[i2 + 1][0] <= w:
            i2 += 1
        if s1[i1][1] >= s2[i2][1]:
            val = s1[i1][1]
            com = s1[i1][2]
        else:
            val = s2[i2][1]
            com = s2[i2][2]
        if len(ret) >= 1 and ret[-1][1] >= val:
            continue
        ret.append((w, val, com))
    return ret



N = int(input())
A = [int(_) for _ in input().split()]

parent = [0] * (N + 1)
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    parent[v] = u

#print(parent)

ret = [None] * (N + 1)
ret[0] = [(0, 0, None)]
for i in range(1, N + 1):
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    #print(ret[i])
    print(ret[i][-1][1])

#print(ret)

Submission status: Runtime Error

Solution code:
def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    w_set = set([_[0] for _ in s1])
    w_set = w_set.union([_[0] for _ in s2])
    w_set = list(w_set)
    w_set.sort()
    i1 = 0
    i2 = 0
    ret = []
    for w in w_set:
        while i1 + 1 < len(s1) and s1[i1 + 1][0] <= w:
            i1 += 1
        while i2 + 1 < len(s2) and s2[i2 + 1][0] <= w:
            i2 += 1
        if s1[i1][1] >= s2[i2][1]:
            val = s1[i1][1]
            com = s1[i1][2]
        else:
            val = s2[i2][1]
            com = s2[i2][2]
        if len(ret) >= 1 and ret[-1][1] >= val:
            continue
        ret.append((w, val, com))
    return ret



N = int(input())
A = [int(_) for _ in input().split()]

parent = [0] * (N + 1)
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    parent[v] = u

print(parent)

ret = [None] * (N + 1)
ret[0] = [(0, 0, None)]
for i in range(1, N + 1):
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    #print(ret[i])
    print(ret[i][-1][1])

#print(ret)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from bisect import *

def dfs(v, pv):
    j = bisect_left(dp, a[v])
    prev = dp[j]
    dp[j] = a[v]
    ans[v] = bisect_left(dp, 10**18)-1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs(nv, v)
    
    dp[j] = prev

N = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(N)]

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

dp = [10**18]*(N+1)
dp[0] = -10**18
ans = [-1]*N
dfs(0, -1)

for ans_i in ans:
    print(ans_i)

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left

def dfs(v, p=-1):
    a = A[v]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a

    ans[v] = bisect_left(LIS, INF)

    for u in G[v]:
        if u == p:
            continue
        dfs(u, v)
    
    LIS[idx] = old_val

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = [INF] * N
ans = [0] * N

dfs(0)

print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    if u > v:
        u, v = v, u
    G[u-1].append(v-1)
LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None)) # (current_node, prev_node, old_val)
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        LIS[p_node] = old_val
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        stack.append((next_node, c_node, old_val))
    
    print(LIS)

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None))
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        print(c_node, p_node, old_val)
        LIS[p_node] = old_val
        print(c_node, LIS)
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)
    print(c_node, LIS)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        stack.append((next_node, c_node, old_val))

print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
#coding:utf-8

N = int(input())
A = input().split()

group = [[].copy() for i in range(N+1)]

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

for i in group:
    i.sort()

data = [0] * (N + 1)
route = []
poute = []
ans = []

def explore(target,address = 1):
    
    data[address] = 1
    route.append(address)
    
    if route[-1] == target:
        for h in route:
            poute.append(h)
    
    for i in group[address]:
        if data[i] == 0:
            explore(target,i)
    route.remove(address)

def bisect_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo


path = []
L = 0

for i in range(1,N+1):
    data = [0] * (N + 1)
    route = []
    poute = []
    explore(i)
    path = poute
    L = len(path)
    dp = [float('inf')] * L
    for i in path:
        j = int(A[i-1])
        index = bisect_left(dp,j)
        dp[index] = j
    M = bisect_left(dp,float('inf'))
    print("{}".format(M))

Submission status: Runtime Error

Solution code:
#coding:utf-8

N = int(input())
A = input().split()

group = [[].copy() for i in range(N+1)]

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

for i in group:
    i.sort()

print(group)

data = [0] * (N + 1)
route = []
poute = []
ans = []

def explore(target,address = 1):
    
    data[address] = 1
    route.append(address)
    
    if route[-1] == target:
        for h in route:
            poute.append(h)
    
    for i in group[address]:
        if data[i] == 0:
            explore(target,i)
    route.remove(address)

def bisect_left(a, x, lo=0, hi=None):

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid] < x: lo = mid+1
        else: hi = mid
    return lo


path = []
L = 0

for i in range(1,N+1):
    data = [0] * (N + 1)
    route = []
    poute = []
    explore(i)
    path = poute
    L = len(path)
    dp = [float('inf')] * L
    for i in path:
        j = int(A[i-1])
        index = bisect_left(dp,j)
        dp[index] = j
    M = bisect_left(dp,float('inf'))
    print("{}".format(M))

Submission status: Runtime Error

Solution code:
#coding:utf-8
from bisect import bisect_left

N = int(input())
A = input().split()

group = [[].copy() for i in range(N+1)]

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

for i in group:
    i.sort()

print(group)

data = [0] * (N + 1)
route = []
poute = []
ans = []

def explore(target,address = 1):
    
    data[address] = 1
    route.append(address)
    
    if route[-1] == target:
        for h in route:
            poute.append(h)
    
    for i in group[address]:
        if data[i] == 0:
            explore(target,i)
    route.remove(address)

path = []
L = 0

for i in range(1,N+1):
    data = [0] * (N + 1)
    route = []
    poute = []
    explore(i)
    path = poute
    L = len(path)
    dp = [float('inf')] * L
    for i in path:
        j = int(A[i-1])
        index = bisect_left(dp,j)
        dp[index] = j
    M = bisect_left(dp,float('inf'))
    print("{}".format(M))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# F

import sys
from bisect import bisect_left
# 再起回数上限変更
sys.setrecursionlimit(10000000)


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

# nodes
d = {}
for i in range(N):
    d[i] = []

# set vertex information
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    d[a].append(b)

# print(d)

dp = [float('inf')] * N
dp[0] = -float('inf')

res = [0] * N
max_a = 10**9 + 5


def dfs(node):
    global dp

    # 自分の値
    val = A[node]
    idx = bisect_left(dp, val)
    # 更新前の値を保持する
    prev = {'node':idx, 'val': dp[idx]}

    # update
    dp[idx] = val
    res[node] = bisect_left(dp, max_a) - 1
    # print(node, res[node], d[node])

    for node in d[node]:
        dfs(node)

    # roll back
    dp[prev['node']] = prev['val']


dfs(0)

for res in res:
    print(res)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
# F

import sys
from bisect import bisect_left
# 再起回数上限変更
sys.setrecursionlimit(1000000)


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

# nodes
d = {}
for i in range(N):
    d[i] = []

# set vertex information
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    d[a].append(b)

# print(d)

dp = [float('inf')] * N
dp[0] = -float('inf')

res = [0] * N
max_a = 10**9 + 5


def dfs(node):
    global dp

    # 自分の値
    val = A[node]
    idx = bisect_left(dp, val)
    # 更新前の値を保持する
    prev = {'node':idx, 'val': dp[idx]}

    # update
    dp[idx] = val
    res[node] = bisect_left(dp, max_a) - 1
    # print(node, res[node], d[node])

    for node in d[node]:
        dfs(node)

    # roll back
    dp[prev['node']] = prev['val']


dfs(0)

for res in res:
    print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
import sys
import bisect

INF = 1145141919

a = []
dp = []
ans = []
T = []


def dfs(v: int, p: int):
    index = bisect.bisect_left(dp, a[v])
    dp[index], a[v] = a[v], dp[index]

    ans[v] = bisect.bisect_left(dp, INF)

    for u in T[v]:
        if u != p:
            dfs(u, v)

    dp[index], a[v] = a[v], dp[index]


def solve(N: int, tmp_a: "List[int]", tmp_T: "List[List[int]]"):
    global dp, ans, a, T
    dp = [INF] * N
    ans = [0] * N
    a = tmp_a
    T = tmp_T

    dfs(0, -1)

    print("\n".join(map(str, ans)))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [[] for _ in range(N)]  # type: "List[List[int]]"
    for i in range(N - 1):
        u = int(next(tokens)) - 1
        v = int(next(tokens)) - 1
        T[u].append(v)
        T[v].append(u)
    solve(N, a, T)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    T[u].add(v)
    T[v].add(u)

search = [0]*N

A = [INF]

ans = [-1]*N

def dfs(V):
    num = a[V]
    added = 0
    if A[-1] > num:
        A.append(num)
        added = 1
    else:
        k = bisect.bisect_left(A,num)
        v = A[k]
        A[k] = num
    ans[V] = len(A)
    for VV in T[V]:
        if search[VV]:
            continue
        search[VV] = 1
        dfs(VV)
    if added:
        A.pop()
    else:
        A[k] = v

search[0] = 1
dfs(0)

print(*ans,sep="\n")

Submission status: Runtime Error

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

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    T[u].add(v)
    T[v].add(u)

A = [INF]*N

ans = [-1]*N

def dfs(V):
    num = a[V]
    k = bisect.bisect_left(A,num)
    v = A[k]
    A[k] = num
    ans[V] = bisect.bisect_left(A,INF)
    # このにぶたん無駄じゃね？まあ間に合うからいいか……
    for VV in T[V]:
        dfs(VV)
        T[VV].remove(V)
    A[k] = v

dfs(0)

print(*ans,sep="\n")