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 bisect
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

stack = [0]
dp = [0] * n
que = [] * n
pre = [0] * n
dp = [-1] * n
dp[0] = 0
ans = [0] * n
ans[0] = 1
def bfs(n):
  global stack
  global que
  global dp
  global pre
  
  if len(stack) == 0:return
  u = stack.pop()
  n = dp[u] +1
  que.append(u)
  for v in uv[u]:
    if dp[v] == -1:
      stack.append(v)
      dp[v] = n
      pre[v] = u
      if a[u] < a[v]:
        ans[v] = ans[u] + 1
      else:
        ans[v] = ans[u]
  bfs(n)

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

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

stack = deque([0])
dp = [0] * n
dp[0] = 1
cl = uv[0]

def bfs(u):
  global dp
  global stack
  global cl
  #if u in cl:
  #  o = stack.pop()
  #  stack.append(0)
  #  stack.append(o)
  for v in uv[u]:
    if dp[v] == 0 or dp[v] > dp[u]:
      dp[v] = dp[u] +1
      if len(stack) > 0:
        o = stack.pop()
        if o != u:
          stack.append(o)
          stack.append(-1)
          stack.append(u)
        else:
          stack.append(o)
      stack.append(v)
      bfs(v)

bfs(0)

ans = [0] * n
while stack:
  x = stack.popleft()
  if x == 0:
    ans[x] = 1
    pre = 0
  elif x == -1 or pre == -1:
    pass
  elif a[pre] < a[x] and (ans[x] <= ans[pre] or ans[x] == 0):
    ans[x] = ans[pre] + 1
  else:
    ans[x] = ans[pre]
  pre = x

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

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

stack = deque([0])
dp = [0] * n
dp[0] = 1
cl = uv[0]

def bfs(u):
  global dp
  global stack
  global cl
  #if u in cl:
  #  o = stack.pop()
  #  stack.append(0)
  #  stack.append(o)
  for v in uv[u]:
    if dp[v] == 0 or dp[v] > dp[u]:
      dp[v] = dp[u] +1
      if len(stack) > 0:
        o = stack.pop()
        if o != u:
          stack.append(o)
          stack.append(-1)
          stack.append(u)
        else:
          stack.append(o)
      stack.append(v)
      bfs(v)

bfs(0)

ans = [0] * n
while stack:
  x = stack.popleft()
  if x == 0:
    ans[x] = 1
    pre = 0
  elif x == -1 or pre == -1:
    pass
  elif a[pre] < a[x] and (ans[x] <= ans[pre] or ans[x] == 0):
    ans[x] = ans[pre] + 1
  else:
    ans[x] = ans[pre]
  pre = x

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
dp = [0] * n
dp[0] = 1
ans[0] = 1
def bfs(x):
  global dp
  if x >= n:
    return
  for i in uv[x]:
    if (dp[i] == 0) or (dp[i] <= (dp[x] + 1) and (ans[i] > ans[x])):
      if a[x] < a[i]:
        ans[i] = ans[x] + 1
      else:
        ans[i] = ans[x]
      dp[i] = dp[x] + 1
      bfs(i)

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

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
dp = [0] * n
at = [0] * n
dp[0] = 1
ans[0] = 1
def bfs(x):
  global dp
  for i in uv[x]:
    if (dp[i] == 0) or (dp[i] <= (dp[x] + 1) and (ans[i] > ans[x])):
      if a[x] < a[i]:
        ans[i] = ans[x] + 1
      else:
        ans[i] = ans[x]
      dp[i] = dp[x] + 1
      bfs(i)

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

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
que = deque([0])
ans[0] = 1
def dfs(x):
  global ans
  ansx = ans[x]
  ax = a[x]
  for i in uv[x]:
    if ans[i] == 0:
      if ax < a[i]:
        ans[i] = ansx + 1
      else:
        ans[i] = ansx
      que.append(i)
      while que:
        nx = que.popleft()
        dfs(nx)
  
dfs(0)
for i in range(n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
que = deque([0])
ans[0] = 1
def dfs(x):
  global ans
  if ans.count(0) == 0:
    return
  ansx = ans[x]
  ax = a[x]
  for i in uv[x]:
    if ans[i] == 0:
      if ax < a[i]:
        ans[i] = ansx + 1
      else:
        ans[i] = ansx
      que.append(i)
  while que:
    nx = que.popleft()
    dfs(nx)
  
dfs(0)
for i in range(n):
  print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
que = deque([0])
ans[0] = 1
def dfs(x):
  global ans
  ansx = ans[x]
  ax = a[x]
  for i in uv[x]:
    if ans[i] == 0:
      if ax < a[i]:
        ans[i] = ansx + 1
      else:
        ans[i] = ansx
      que.append(i)
    while que:
      nx = que.popleft()
      dfs(nx)
  
dfs(0)
for i in range(n):
  print(ans[i])

Submission status: Runtime Error

Solution code:

from bisect import bisect_left
n  = int(input())
A = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
dp = [0] * n
que = []
def dfs(i):
  global dp
  global ans
  a = A[i]
  dp[i] = 1
  for u in uv[i]:
    if dp[u] == 0:
      dp[u] = 1
      if a < A[u]:
        ans[u] = ans[i] + 1
      else:
        ans[u] = ans[i]
      que.append(u)
  while que:
    ni = que.pop()
    dfs(ni)

ans[0] = 1
dfs(0)

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
n  = int(input())
A = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
dp = [0] * n
que = []
def dfs(i):
  a = A[i]
  dp[i] = 1
  for u in uv[i]:
    if dp[u] == 0:
      dp[u] = 1
      if a < A[u]:
        ans[u] = ans[i] + 1
      else:
        ans[u] = ans[i]
      que.append(u)
  while que:
    ni = que.pop()
    dfs(ni)

ans[0] = 1
dfs(0)

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

Submission status: Runtime Error

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

ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  ansx = ans[x]
  ax = a[x]
  for i in uv[x]:
    if ans[i] == 0:
      if ax < a[i]:
        ans[i] = ansx + 1
      else:
        ans[i] = ansx
      que.append(i)
  

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

Submission status: Runtime Error

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

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


ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  ansx = ans[x]
  ax = a[x]
  for i in range(n):
    if uv[x][i] == 1:
      if ans[i] == 0:
        ai = a[i]
        if ai > ax:
          ans[i] = ansx + 1
        else:
          ans[i] = ansx
        que.append(i)
  return ans

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

Submission status: Runtime Error

Solution code:
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u][v] = 1
  uv[v][u] = 1

ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  ansx = ans[x]
  ax = a[x]
  for i in range(n):
    ansi = ans[i]
    ai = a[i]
    if uv[x][i] == 1 and ansi == 0:
      ans[i] = ansx
      if ai > ax:ans[i] += 1
      que.append(i)

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

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

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

ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  for i in range(n):
    if uv[x][i] == 1 and ans[i] == 0:
      if a[i] > a[x]:
        ans[i] = ans[x] + 1
      else:
        ans[i] = ans[x]
      que.append(i)

print(ans)

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left as bile

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    arr = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)

    ans = [0]*n
    inf = 1e18
    dp = [inf]*(n+10)
    parent = [-1]*n
    def dfs(s):
        idx = bile(dp, arr[s])
        tmp = dp[idx]
        dp[idx] = arr[s]
        ans[s] = bile(dp, inf)

        for v in adj[s]:
            if v == parent[s]:
                continue
            parent[v] = s
            dfs(v)
        dp[idx] = tmp
        return ans
        
    ans = dfs(0)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left as bile

    # while stack:
    #     node = stack.pop()
    #     for v in adj[node]:
    #         if v == parent[node]:
    #             continue
    #         parent[v] = node
    #         stack.append(v)
    #     dp
    

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    arr = list(map(int, input().split()))
    adj = [[] for _ in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        adj[a].append(b)
        adj[b].append(a)

    ans = [0]*n
    inf = 1e18
    dp = [inf]*n
    parent = [-1]*n
    def dfs(s):
        
        idx = bile(dp, arr[s])
        tmp = dp[idx]
        dp[idx] = arr[s]
        ans[s] = bile(dp, inf)

        for v in adj[s]:
            if v == parent[s]:
                continue
            parent[v] = s
            dfs(v)
        dp[idx] = tmp
        return ans
        
    ans = dfs(0)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**12
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

#import sys,resource,bisect
from sys import setrecursionlimit
from resource import getrlimit,setrlimit
from bisect import bisect_left
def setrlim():
  setrecursionlimit(250000)
  soft,hard = getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(u,j,dp):
    #ddprint(f"dfs {u=} {j=}")
    ans[u] = j
    for v in dst[u]:
        if ans[v]>=0:
            continue
        x = bisect_left(dp,a[v])
        tmp = dp[x]
        dp[x] = a[v]
        #ddprint(f"dfs {u=} {j=} {x=} {tmp=} av {a[v]} {dp=}")
        dfs(v,j+(1 if tmp==BIG else 0),dp)
        dp[x] = tmp

setrlim()
n = inn()
a = inl()
a[0:0] = [0]
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v = inm()
    dst[u][v] = dst[v][u] = 1
ans = [-1]*(n+1)
dp = [BIG]*(n+1)
dp[0] = a[1]
dfs(1,1,dp)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
from bisect import *
N=int(input())
A=list(map(int,input().split()))
G=[[] for i in range(N)]
u,v=0,0
for i in range(N-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  G[u].append(v)
  G[v].append(u)
P=[0]*N
def dfs(DP,now,prev):
  x=bisect_right(DP,A[now])
  P[now]=x
  y=DP[x]
  DP[x]=A[now]
  for i in range(len(G[now])):
    if G[now][i]!=prev:
      dfs(DP,G[now][i],now)
  DP[x]=y

D=[0]
for i in range(N):
  D.append(10**9+5)
dfs(D,0,0)
for i in range(N):
  print(P[i])

Submission status: Runtime Error

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit
from bisect import bisect_left

#@njit
def main():
    N = int(input())
    a = list(map(int, input().split()))
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, input().split())
        edges[u] += v,
        edges[v] += u,

    ans = [0]*(N+1)
    lastLis = []
    visited = [False]*(N+1)
    parent = {}
    n = 1
    stack = []

    def rec(n):
        nonlocal lastLis,stack
        #print(n, lastLis, stack)
        if not visited[n]:
            if len(lastLis) == 0 or a[n-1] > lastLis[-1]:
                lastLis.append(a[n-1])
                stack += (len(lastLis)-1, -1),
            else:
                index = bisect_left(lastLis, a[n-1])
                stack += (index, lastLis[index]),
                lastLis[index] = a[n-1]
            ans[n] = len(lastLis)
            visited[n] = True
        else:
            pass
        hasNext = False
        for d in edges[n]:
            if not visited[d]:
                parent[d] = n
                rec(d)
                hasNext = True
        # 巻き戻し
        index, value = stack.pop(len(stack)-1)
        if value < 0:
            lastLis.pop(index)
        else:
            lastLis[index] = value

    rec(1)
    for i in range(1, len(ans)):
        print(ans[i])




main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)



def dfs(p):
    ai = a[p]
    i = bisect_left(dp, ai)
    old = dp[i]
    dp[i] = ai
    ans[p] = bisect_left(dp, INF)-1
    for child in to[p]:
        if ans[child] is None:
            dfs(child)
    dp[i] = old
    
    
        

if __name__ == "__main__":
    n = int(input())
    a = [None] + list(map(int, input().split()))
    to = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
    INF = 10**20
    dp = [INF]*(n+1)
    dp[0]= -INF
    q = deque([1])
    ans = [None]*(n+1)
    dfs(1)
    print("\n".join(list(map(str, ans[1:]))))

Submission status: Runtime Error

Solution code:
import bisect as bs

def dfs(i, nbr, A, prv, done, history, B, ans):#深さ優先探索（再帰）
  
  j = bs.bisect_right(B,A[i]) #Bへの挿入予定位置
  #print(i,A[i],j,B)
  
  #A[i]をhistoryの適当な位置に挿入
  if j < len(B):
    history[i] = (B[j], A[i], j) # 更新前の値、更新後の値、更新位置
    B[j] = A[i]
  else:
    history[i] = (-1, A[i], j) # 「追加する」 、追加する値、追加位置（最後）
    B.append(A[i])
  
  ans[i] = len(B) #答え書き込み
  done[i] = 1 #探索済み
  #print(i,B)
  
  for a in nbr[i]:
    if done[a] == 0: #探索前のみ
      dfs(a, nbr, A, prv, done, history, B, ans)
      prv[a] = i
      
  j = history[i][2]
  if history[i][0] >= 0:
    B[j] = history[i][0] #Bを現状復帰
  else:
    B.pop()
    
N = int(input()) 
A = list(map(int,input().split()))

nbr = [[] for _ in range(N)]

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

#print(nbr)
  
prv = [-1 for _ in range(N)]
done = [0 for _ in range(N)] 
history = [0 for _ in range(N)]
B = []
ans = [0 for _ in range(N)]

dfs(0, nbr, A, prv, done, history, B, ans)

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

Submission status: Runtime Error

Solution code:
# LIS on Tree

from collections import deque
import bisect

N = int(input())
V = list(map(int, input().split()))
V.insert(0, 0)
visited = [False for i in range(N+1)]
inf = 10**18
dp = [inf for i in range(N+1)]
ans = [-1 for i in range(N+1)]
stack = deque()

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


def dfs(s_node):
    visited[s_node] = True
    # dp値の更新
    value = V[s_node]
    index = bisect.bisect_left(dp, value)
    old_value = dp[index]
    dp[index] = value
    ans[s_node] = bisect.bisect_right(dp, inf-1)
    stack.append((index, old_value, value))
    for child in G[s_node]:
        if visited[child] == False:
            dfs(child)
    # 帰りがけにバックトラックを行う
    index, old_value, value = stack.pop()
    dp[index] = old_value


dfs(1)

for i in range(1, N+1):
    print(ans[i])

Submission status: Runtime Error

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

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

tree = [[] for _ in range(n)]
for _ 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
visited = [0] * n
visited[0] = 1


def dfs(i, l):
    s = a[i]
    if len(l) == 0 or s > l[-1]:
        l.append(s)
    else:
        l[bisect.bisect_left(l, s)] = s
    ans[i] = len(l)

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni, l[:])


dfs(0, [])

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(j, parent):
    index = bisect_left(dp, a[j])
    old = dp[index]
    dp[index] = a[j]
    ans[j] = bisect_left(dp, INF)-1
    for child in to[a[j]]:
        if child != parent:
            dfs(child, a[j])
    dp[index] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        to[u].append(v)
        to[v].append(u)
    INF = 10**20
    dp = [INF]*(n+1)
    dp[0] = -INF
    ans = [None]*n
    dfs(1, -1)
    print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    if n == 2 and u == 1 and v == 0:
        print("yes")
        exit(0)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    if n == 2 and u == v:
        print("yes")
        exit(0)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(200000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(100000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect, insort

def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect, insort

def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*(2*10**5+1)
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*(2*10**5+1)
    dp[0] = -INF
    dfs(0, -1)
    for i in range(n):
        print(ans[i])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect, insort

def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    INF = 10**10
    ans = [INF]*n
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, bisect, insort

def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = i
    if p != -1:
        ans[v] = max(ans[v], ans[p])
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [None]*n
    INF = 10**10
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Runtime Error

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

tree=[[] for _ in range(n)]
for _ in range(n-1):
    aa,bb=map(int,input().split())
    tree[aa-1].append(bb-1)
    tree[bb-1].append(aa-1)

ans=[0]*n
import bisect

#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

def lisOnTree(x,lis):
    global ans,tree,a,n
    i=bisect.bisect_left(lis, a[x])
    if i==len(lis):
        lis.append(a[x])
        flag="append"
    else:
        flag=(i,lis[i])
        lis[i]=a[x]
    #print(x,lis)
    ans[x]=len(lis)
    for item in tree[x]:
        if ans[item]==0:
            lisOnTree(item,lis)
    if flag=="append":
        lis.pop()
    else:
        lis[flag[0]]=flag[1]

lisOnTree(0,[])

for item in ans:
    print(item)

Submission status: Runtime Error

Solution code:
import sys
import bisect  # 二分法

MAX_N = 200005
INF = 10**9 + 5

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)

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

def dfs(u,r=-1):

    # u を訪れたときの処理
    i = bisect.bisect_left(lis, A[u])  # 
    old = lis[i]  # 書き換え前の値を一時保存
    lis[i] = A[u]

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

        dfs(v,u)
    
    ans[u] = bisect.bisect_left(lis,INF-1)
    lis[i] = old  # 書き換え前の状態に戻す

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

Submission status: Runtime Error

Solution code:
import sys
import bisect  # 二分法

MAX_N = 200005
INF = 10**9 + 5

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)

lis = [INF] * N
lis[0] = 1
ans = [0] * N 

def dfs(u,r=-1):

    # u を訪れたときの処理
    i = bisect.bisect_left(lis, A[u])  # 
    old = lis[i]  # 書き換え前の値を一時保存
    lis[i] = A[u]

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

        dfs(v,u)
    
    ans[u] = bisect.bisect_left(lis,INF-1)
    lis[i] = old  # 書き換え前の状態に戻す

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