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
from bisect import bisect_left
changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [10 ** 20] * N

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append(LIS[changeID])
    LIS[changeID] = A[i]
    Ans[i] = changeID + 1
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backNum = changed.pop()
    LIS[changeID] = backNum
    return 0


def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    

    return 0

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 10000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append((-1, 0))
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k[0] == -1:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append(0)
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k == 0:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline().strip()
n, a, b, c = map(int, input().split())
s = []
for _ in range(n):
    s.append(input())

# 0 <= i < n-1
ans = []
for i in range(n-1):
    if s[i] == 'BC':
        if b > c:
            ans.append('C')
            b -= 1
            c += 1
        elif b < c:
            ans.append('B')
            b += 1
            c -= 1
        elif s[i+1] == 'AB':
            ans.append('B')
            b += 1
            c -= 1
        else:
            ans.append('C')
            b -= 1
            c += 1

    elif s[i] == 'AC':
        if a > c:
            ans.append('C')
            a -= 1
            c += 1
        elif a < c:
            ans.append('A')
            a += 1
            c -= 1
        elif s[i+1] == 'BC':
            ans.append('C')
            a -= 1
            c += 1
        else:
            ans.append('A')
            a += 1
            c -= 1

    else:
        if a > b:
            ans.append('B')
            a -= 1
            b += 1
        elif a < b:
            ans.append('A')
            a += 1
            b -= 1
        elif s[i+1] == 'AC':
            ans.append('A')
            a += 1
            b -= 1
        else:
            ans.append('B')
            a -= 1
            b += 1

    if a < 0 or b < 0 or c < 0:
        print('No')
        exit()

# i = n-1
if s[n-1] == 'BC':
    if b > c:
        ans.append('C')
        b -= 1
        c += 1
    else:
        ans.append('B')
        b += 1
        c -= 1

elif s[n-1] == 'AC':
    if a > c:
        ans.append('C')
        a -= 1
        c += 1
    else:
        ans.append('A')
        a += 1
        c -= 1

else:
    if a > b:
        ans.append('B')
        a -= 1
        b += 1
    else:
        ans.append('A')
        a += 1
        b -= 1

if a < 0 or b < 0 or c < 0:
    print('No')
    exit()

print('Yes')
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))

result = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]
for _i in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    tree[u].append(v)
    tree[v].append(u)
INF = float('inf')
dp = [INF for _i in range(n+1)]


def dfs(p, x):
    i = bisect_left(dp, a[p])
    old = dp[i]
    dp[i] = a[p]
    result[p] = bisect_left(dp, INF)
    for j in tree[p]:
        if j != x:
            dfs(j, p)
    dp[i] = old
    

dfs(0, -1)

for i in result:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left
def input():return sys.stdin.readline().strip()

def main():
    N = int(input())
    A = tuple(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)
    
    ans = [0] * N
    dp = []
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        if idx == len(dp):
            old = -1
            dp.append(a)
        else:
            old = dp[idx]
            dp[idx] = a
        
        ans[now] = len(dp)

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        if old == -1:
            dp.pop()
        else:
            dp[idx] = old

    
    dfs(0, -1)

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

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left
from copy import deepcopy
n = int(input())
a = list(map(int, input().split()))

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

dp = [float('inf') for _i in range(n)]
q = [[0, dp]]
q = deque(q)
while q:
    p, d = q.popleft()
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = d.index(float('inf')-1)
    for i in tree[p]:
        if result[i] < 0:
            q.append([i, deepcopy(d)])

for i in result:
    print(i)

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import *
from copy import deepcopy
n = int(input())
a = list(map(int, input().split()))

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

dp = [float('inf') for _i in range(n)]
q = [[0, dp]]
q = deque(q)
while q:
    p, d = q.popleft()
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = d.index(float('inf')-1)
    for i in tree[p]:
        if result[i] < 0:
            q.append([i, deepcopy(d)])

for i in result:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

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

B = sorted(list(set(A)))
toID = {i:j for i,j  in zip(B,range(1,len(B) + 1))}
dp = SegmentTree([0] * (len(B) + 1))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    flag = False
    if before[v] < a:
        flag = True
        dp.update(idx,a)
    M = dp.query(0,N)
    ans[v] = max(M,a)
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    if flag:
        dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

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

B = sorted(list(set(A)))
toID = {i:j for i,j  in zip(B,range(1,len(B) + 1))}
dp = SegmentTree([0] * (len(B) + 1))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    dp.update(idx,a)
    M = dp.query(0,N)
    ans[v] = max(M,a)
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from collections import deque
"""
行き ⇨ dp LIS計算とstack登録
帰り ⇨ stackをpop dp巻き戻し
"""

n = int(input())
As = list(map(int, input().split()))
edges = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)
    edges[v].append(u)


INF = 10**10
dp = []
pos = 0
ans = [0] * n
q = deque([])
def dfs(v,p):
    global pos
    # 行き
    a = As[v]
    ind = bisect_left(dp, a)
    if ind == len(dp): 
        dp.append(a)
        # 引数の1つ目はappendしたか
        q.append((True, -1, -1))
    else:
        # 更新
        tmp = dp[ind]
        dp[ind] = a
        q.append((False,ind,tmp))

    ans[v] = len(dp)
    for u in edges[v]:
        if u == p:continue
        dfs(u,v)
        # 帰り        
        isappend, ind, tmp = q.pop()
        if isappend:
            dp.pop()
        else:
            dp[ind] = tmp
        
    
dfs(0,-1)

print(*ans)

Submission status: Runtime Error

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)
n = int(input())
a = [0]+list(map(int,input().split()))
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
  u,v = map(int,input().split())
  tree[u].append(v)
  tree[v].append(u)
#print(tree)
d = [float("inf")]*(n+1)
ans = [0]*(n+1)

def dfs(now, pre):
  print(now,pre)
  i = bisect.bisect_left(d, a[now])
  tmp = d[i]
  d[i] = a[now]
  ans[now] = bisect.bisect_left(d, float("inf"))
  print(d)
  for nxt in tree[now]:
    if nxt == pre:
      continue
    dfs(nxt, now)
  d[i] = tmp
dfs(1,-1)

for i in ans[1:]:
  print(i)

Submission status: Runtime Error

Solution code:
import bisect

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

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

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    for child in rooted[node]:
        dfs(child)
    table[p] = old
    lis[node] = p + 1

dfs(0)
print(*map(str, lis), sep="\n")

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def make_order(g, v):
    seen = [False]*g.N
    pre_order = [-1]*g.N
    post_order = [-1]*g.N
    counters = {"pre": 0, "post": 0}

    parent = [-1]*g.N

    def recur(v):
        pre_order[counters["pre"]] = v
        counters["pre"] += 1

        seen[v] = True
        for to, w in g.E[v]:
            if seen[to] == True:
                continue
            parent[to] = v
            recur(to)

        post_order[counters["post"]] = v
        counters["post"] += 1

    recur(v)
    return pre_order, post_order


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []

    pre_order, post_order = make_order(g, 0)
    # print(pre_order, post_order, parent, sep="\n")
    post_order += [-1]
    post = 0
    seen = [False]*(N+10)
    # return

    for i, curr in enumerate(pre_order):
        # print(i, curr, dp, event)
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:bisect_left(dp, INF)])
        seen[curr] = True

        while seen[post_order[post]]:
            c, i, v = event.pop()
            dp[i] = v
            post += 1

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

    return


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]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def make_order(g, v):
    seen = [False]*g.N
    pre_order = [-1]*g.N
    post_order = [-1]*g.N
    counters = {"pre": 0, "post": 0}

    parent = [-1]*g.N

    def recur(v):
        pre_order[counters["pre"]] = v
        counters["pre"] += 1

        seen[v] = True
        for to, w in g.E[v]:
            if seen[to] == True:
                continue
            parent[to] = v
            recur(to)

        post_order[counters["post"]] = v
        counters["post"] += 1

    recur(v)
    return pre_order, post_order, parent


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []

    pre_order, post_order, parent = make_order(g, 0)
    # print(pre_order, post_order, parent, sep="\n")
    post_order += [N]
    post = 0
    seen = [False]*(N+1)
    # return

    for i, curr in enumerate(pre_order):
        # print(i, curr, dp, event)
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:bisect_left(dp, INF)])

        seen[curr] = True

        while seen[post_order[post]]:
            c, i, v = event.pop()
            dp[i] = v
            post += 1

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

    return


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]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+1)
    dp[0] = -float('inf')
    dp2 = [0] * (N+1)
    paths = []
    actions = []# (idx, pre, pro)
    def dfs(node, parent=None):
        a = A[node]
        seen[node] = True
        if parent == None:
            paths.append(node)
            actions.append((1, dp[1], a))
            dp[1] = a
        else:
            while True:
                tmp = paths.pop()
                if tmp == parent:
                    paths.append(tmp)
                    paths.append(node)
                    break
                else:
                    idx, pre, pro = actions.pop()
                    dp[idx] = pre


            idx = bin_search(dp[:len(paths)+1], a)
            if idx == float('inf'):
                actions.append((len(paths), float('inf'), a))
                dp[len(paths)] = a
            else:
                actions.append((idx, dp[idx], a))
                dp[idx] = a
        print(dp.index(float('inf'))-1)
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)
    dfs(1)


    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
stack=deque([])
lis=[]
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    if len(lis)==0 or lis[-1]<a[s]:
        lis.append(a[s])
        stack.append((len(lis)-1,-1))
    else:
        #print(lis)
        idx=bisect_right(lis,a[s])
        #print(idx)
        stack.append((idx,lis[idx]))
        lis[idx]=a[s]
    ans[s]=len(lis)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    if val==-1:
        del lis[-1]
    else:
        lis[idx]=val
dfs(0)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edge[u].append(v)
  edge[v].append(u)
ans=[-1]*n
dp=[10**10]*n

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
#木構造を投げると訪問順listが帰ってくる、|ans|=2*n-1
#適宜書き換えて実装を楽にしましょう
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    ind=bisect_right(dp,a[i])
    bef=dp[ind]
    dp[ind]=a[i]
    ans[i]=bisect_left(dp,10**10)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[ind]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)


root = 0

ans = [0] * N
check = [False] * N
check[root] = True

memo = [None] * N

INF = 10 ** 10
dp = [INF] * N

def dfs(x):
    tmp = bisect_left(dp, A[x])
    memo[x] = (tmp, dp[tmp])
    dp[tmp] = A[x]
    ans[x] = bisect_left(dp, INF)
    for next_ in G[x]:
        if check[next_]:
            continue
        check[next_] = True
        dfs(next_)
    j, a = memo[x]
    dp[j] = a

dfs(root)

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_right(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

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

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().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)
    graph[v].append(u)
ans = [0 for _ in range(N)]
import sys
from typing import List
sys.setrecursionlimit(10**7)
def recursion(ind, dp:List[int] , visited):
    if visited[ind] > 0 : return
    if len(dp) == 0 or dp[-1] < a[ind]:
        dp.append(a[ind])
        visited[ind] = len(dp)
        for v in graph[ind]:
            recursion(v,dp,visited)
        dp.pop()
        return
    else :
        left, right = 0, len(dp)
        while right - left > 1:
            mid = (right + left) //2
            if dp[mid] < a[ind]:
                left = mid
            else :
                right = mid

        tmp = dp[left+1]
        dp[left+1] = min(tmp, a[ind])
        visited[ind] = left + 2
        for v in graph[ind]:
            recursion(v, dp, visited)
        dp[left+1] = tmp
recursion(0, [], ans)
for t in ans:
    print(t)

Submission status: Runtime Error

Solution code:
N = int(input())
a = list(map(int, input().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)
    graph[v].append(u)
ans = [0 for _ in range(N)]
import sys
from typing import List
sys.setrecursionlimit(10**7)
def recursion(ind, dp:List[int] , visited):
    if visited[ind] > 0 : return
    print(ind+1, dp, visited)
    if len(dp) == 0 or dp[-1] < a[ind]:
        dp.append(a[ind])
        visited[ind] = len(dp)
        for v in graph[ind]:
            recursion(v,dp,visited)
        dp.pop()
        return
    else :
        left, right = 0, len(dp)
        while right - left > 1:
            mid = (right + left) //2
            print(left, right, dp[mid], a[ind])
            if dp[mid] < a[ind]:
                left = mid
            else :
                right = mid

        tmp = dp[left+1]
        dp[left+1] = min(tmp, a[ind])
        visited[ind] = left + 2
        for v in graph[ind]:
            recursion(v, dp, visited)
        dp[left+1] = tmp
recursion(0, [], ans)
for t in ans:
    print(t)

Submission status: Runtime Error

Solution code:
n,a,b,c = [int(i) for i in input().split(" ")]
s=[]
# AB,BC,AC=0
for i in range(n):
    s.append(input())
    # if s[i]=="AB":
    #     AB+=1
    #
    # elif s[i]=="AC":
    #     AC+=1
    #
    # elif s[i] == "BC":
    #     BC+=1

for str in s:
    if str == "AB":
        if a > b:
            a -= 1
            b +=1
            print("B")
        else:
            b-=1
            a +=1
            print("A")
    if str == "AC":
        if a > c:
            a-=1
            c+=1
            print("C")
        else:
            a+=1
            c-=1
            print("A")
    if str == "BC":
        if b > c:
            b-=1
            c+=1
            print("C")
        else:
            b+=1
            c-=1
            print("B")

Submission status: Runtime Error

Solution code:
import numpy as np
print(np.nan)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python3

import sys
import resource

sys.setrecursionlimit(1000000)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, st, dp, nbs):
    ca = a[cur]
    
    for i in range(n):
        if dp[i] > ca:
            st.append((i, dp[i], ca))
            dp[i] = ca
            mlen[cur] = i + 1
            break

    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, st, dp, nbs)

    (idx, ov, nv) = st.pop()
    dp[idx] = ov
    return


n = int(input())
a = tuple(map(int, input().split()))

nbs = [ [] for i in range(n) ]

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


mlen = [ 0 for i in range(n) ]
st = []
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, st, dp, nbs)

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