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: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
import bisect

n = int(input())
A = list(map(int, input().split()))
T = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    T[u].append(v)
    T[v].append(u)
L = [0]*n
INF = 2**31 - 1
def dfs(v, par, B):
    B[bisect.bisect_left(B, A[v])] = A[v]
    L[v] = bisect.bisect_left(B, INF)
    for nv in T[v]:
        if nv != par:
            dfs(nv, v, B.copy())
dfs(0, -1, [INF]*n)
print(*L, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(300000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [999999999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from bisect import bisect_left as bl
def main(n,a):
  ans=[0]*n
  ki=[[] for _ in range(n)]
  for _ in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append(v)
    ki[v].append(u)
  inf=float('inf')
  p={}
  dp=[inf]*(n+1)
  dp[0]=0
  # dp[i]:長さiのLISの末尾の数値の最小値
  maxa=max(a)+1

  def dfs(v,p,dp):
    x=a[v]
    idx=bl(dp,x)
    tmp=dp[idx]
    dp[idx]=x
    # ans[v]=idx こっちだと頂点vで終わるLISの長さになる。下が正しい
    ans[v]=bl(dp,maxa)-1
    for nv in ki[v]:
      if nv==p:continue
      dfs(nv,v,dp)
    dp[idx]=tmp
  dfs(0,-1,dp)
  print(*ans,sep='\n')

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
INF=10**20
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(a0):
    seen =[0]*len(G)
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            idx = bisect_left(lis,A[a])
            his[a] = (idx,lis[idx])
            lis[idx] = A[a]
            dp[a] = bisect_left(lis,INF)
            for b in G[a]:
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          idx,val = his[~a]
          lis[idx] = val
    return
  
lis = [INF]*N
dp = [0]*N
his = {}
dfs(0)
print(*dp,sep="\n")

Submission status: Accepted

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

def dfs(v):
 #DFSの行き(子ノードに下っていくとき)の処理
 pos=bisect.bisect_left(dp,arr[v]) #最長増加部分列で更新する場所を2分探索により求める
 changes.append((pos,dp[pos])) #更新した要素とその値を記録しておく
 dp[pos]=arr[v]
 ans[v]=bisect.bisect_left(dp,10**18) #1からvまでの最長増加部分列の長さは、最長増加部分列の10**18以外の値の個数に等しい
 for u in g[v]:
   if checked[u]==0:
     checked[u]=1
     dfs(u)
 #DFSの戻り(親ノードに上っていくとき)の処理
 pos,val=changes.pop() #頂点vで更新した最長増加部分列の値を元に戻す
 dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
 a,b=map(int,input().split())
 g[a].append(b)
 g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)] #最長増加部分列を求めるのに、十分大きな値で初期化しておく
changes=[]
dfs(1)
for i in range(1,n+1):
 print(ans[i])

Submission status: Accepted

Solution code:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

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

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# 頂点1から頂点kまでの最短パス上
# ルートはO(n)で求められる
N = getN()
A = getList()
query = [getList() for i in range(N - 1)]

dist = [[] for i in range(N)]
for i in range(N - 1):
    a, b = query[i]
    dist[a - 1].append(b - 1)
    dist[b - 1].append(a - 1)

ignore = [0] * N
ignore[0] = 1
lis = [A[0]]
rec = [0] * N
rec[0] = 1

# 行きがけ帰りがけの要領
def dfs(u):
    global lis
    for i in dist[u]:
        if ignore[i] != 1:
            ignore[i] = 1
            # 巻き戻し用
            plus = 0 # true or false
            change = (0, 0, 0) # true or false, 変更した場所、変更した数値

            if A[i] > lis[-1]:
                lis.append(A[i])
                plus = 1
            else:
                index = bisect_left(lis, A[i])
                change = (1, index, lis[index])
                lis[index] = A[i]
            rec[i] = len(lis)
            dfs(i)
            # 巻き戻す
            if plus:
                lis.pop()
            else:
                lis[change[1]] = change[2]

dfs(0)
for i in rec:
    print(i)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(1<<30)
def dfs(i,LIS):
    if a[i] > LIS[-1]:
        LIS.append(a[i])
        ans[i] = len(LIS)
        for j in edges[i]:
            if parent[i] != j:
                parent[j] = i
                dfs(j,LIS)
        LIS.pop()
    else:
        index = bisect.bisect_left(LIS, a[i])
        x = LIS[index]
        LIS[index] = a[i]
        ans[i] = len(LIS)
        for j in edges[i]:
            if parent[i] != j:
                parent[j] = i
                dfs(j,LIS)
        LIS[index] = x

N = int(input())
a = [0]+list(map(int,input().split()))
edges = [[] for _  in range(N+1)]
ans = [-1]*(N+1)
parent = [-1]*(N+1)
for i in range(N-1):
    u,v = map(int,input().split())
    edges[u].append(v)
    edges[v].append(u)
LIS = [a[1]]
dfs(1,LIS)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
## まきもどし？
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
import sys
sys.setrecursionlimit(10**6)
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)
#print(tree)
def isok(num,val):##適宜変更
    return num<val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ
def LIS_1(x,ls,right):##right ::これまでわかっている右端
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret= idx+1
    else:
        ret=right
    rewind_idxval.append((idx,ls[idx]))
    ls[idx]=x
    #print(x,ls)
    return ret
def DFS_LIS(prev,ls,right):
    ans[prev]= LIS_1(A[prev],ls,right)
    for node in tree[prev]:
        if not visited[node]:
            visited[node]=True
            DFS_LIS(node,ls,ans[prev])
    #rewind
    idx,pval = rewind_idxval.pop()
    ls[idx] = pval

ans = [0]*n
s = 0
right=0
rewind_idxval=collections.deque()
visited=[False]*n
visited[s]=True
ls=[INF]*n
DFS_LIS(s,ls,right)
#print(ls)
for a in ans :
    print(a)

Submission status: Accepted

Solution code:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N = I()
A = IL()
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = IL()
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
def dfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  LIS = [INF] * N
  LISmemo = [None] * N
  ans = [None] * N
  q = deque([start])
  while q:
    u = q.pop()
    if u >= 0:
      p = bisect.bisect_left(LIS,A[u])
      LISmemo[u] = (p,LIS[p])
      LIS[p] = A[u]
      ans[u] = bisect.bisect_left(LIS,INF)
      q.append(~u)
      for v in graph[u]:
        if d[v] != INF: continue
        d[v] = d[u] + 1
        q.append(v)
    else:
      if u == ~0: continue
      p,a = LISmemo[~u]
      LIS[p] = a
      
  return ans

ans = dfs(graph,0)

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from bisect import bisect_left
def main(N,a,tr):
  ans=[0]*N
  dp=[float('inf')]*(N+1)
  dp[0]=0
  maxa=max(a)+1
  def dfs(p,v,dp):
    i=bisect_left(dp,a[v])
    tmp=dp[i]
    dp[i]=a[v]
    ans[v]=bisect_left(dp,maxa)-1
    for nv in tr[v]:
      if nv!=p:
        dfs(v,nv,dp)
    dp[i]=tmp
  dfs(-1,0,dp)
  print(*ans,sep='\n')
if __name__=='__main__':
  N=int(input())
  a=list(map(int,input().split()))
  tr=[[] for _ in range(N)]
  for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    tr[u].append(v)
    tr[v].append(u)
  main(N,a,tr)

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def solve(N, A, UV):
    G = [[0] * 0 for _ in range(N)]
    for i in range(N-1):
        u, v = UV[i]
        G[u].append(v)
        G[v].append(u)
    L = [A[0]]
    Ans = np.zeros(N, dtype=np.int64)
    stack = np.zeros((202020, 5), dtype=np.int64)  # 頂点、状態、見ている子のインデックス、行った行動*2
    idx_stack = 0
    while idx_stack >= 0:
        v, state, idx_Gv, idx_L, old = stack[idx_stack]
        idx_stack -= 1
        if state == 0:
            Ans[v] = len(L)
        if state == 2:
            if idx_L == -1:
                del L[-1]
            else:
                L[idx_L] = old
        Gv = G[v]
        if len(Gv) == idx_Gv:
            continue
        u = Gv[idx_Gv]
        G[u].remove(v)
        Au = A[u]
        if Au > L[-1]:
            L.append(Au)
            idx_stack += 1
            stack[idx_stack] = (v, 2, idx_Gv + 1, -1, -1)
            idx_stack += 1
            stack[idx_stack] = (u, 0, 0, -1, -1)
            continue
        else:
            idx_L = np.searchsorted(L, Au)
            old = L[idx_L]
            L[idx_L] = Au
            idx_stack += 1
            stack[idx_stack] = (v, 2, idx_Gv + 1, idx_L, old)
            idx_stack += 1
            stack[idx_stack] = (u, 0, 0, -1, -1)
            continue
    return Ans

numba_compile([
    [solve, "i8[:](i8,i8[:],i8[:,:])"]
])

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    UV = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    Ans = solve(N, A, UV)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Accepted

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import sys
import numpy as np

def solve(N, A, UV):
    G = [[0] * 0 for _ in range(N)]
    for i in range(N-1):
        u, v = UV[i]
        G[u].append(v)
        G[v].append(u)
    L = [A[0]]
    Ans = np.zeros(N, dtype=np.int64)
    stack = [(0, 0, 0, -1, -1)]  # 頂点、状態、見ている子のインデックス、行った行動*2
    while stack:
        v, state, idx_Gv, idx_L, old = stack.pop()
        if state == 0:
            Ans[v] = len(L)
        if state == 2:
            if idx_L == -1:
                del L[-1]
            else:
                L[idx_L] = old
        Gv = G[v]
        if len(Gv) == idx_Gv:
            continue
        u = Gv[idx_Gv]
        G[u].remove(v)
        Au = A[u]
        if Au > L[-1]:
            L.append(Au)
            stack.append((v, 2, idx_Gv + 1, -1, -1))
            stack.append((u, 0, 0, -1, -1))
            continue
        else:
            idx_L = np.searchsorted(L, Au)
            old = L[idx_L]
            L[idx_L] = Au
            stack.append((v, 2, idx_Gv + 1, idx_L, old))
            stack.append((u, 0, 0, -1, -1))
            continue
    return Ans

numba_compile([
    [solve, "i8[:](i8,i8[:],i8[:,:])"]
])

def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = np.array(input().split(), dtype=np.int64)
    UV = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    Ans = solve(N, A, UV)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
def main():
    sys.setrecursionlimit(202020)
    N = int(input())
    A = [0] + list(map(int, input().split()))
    G = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        G[u].append(v)
        G[v].append(u)
    L = [A[1]]
    Ans = [0] * (N+1)
    def dfs(v):
        Ans[v] = len(L)
        for u in G[v]:
            G[u].remove(v)
            Au = A[u]
            if Au > L[-1]:
                L.append(Au)
                dfs(u)
                del L[-1]
            else:
                idx = bisect_left(L, Au)
                old = L[idx]
                L[idx] = Au
                dfs(u)
                L[idx] = old
    dfs(1)
    print("\n".join(map(str, Ans[1:])))

main()

Submission status: Accepted

Solution code:

import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u, v = v, u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])
    tree[uv[1]].append(uv[0])
    

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        for child in tree[cur]:
            if used[child] == 0:
                queue.append(child)
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1
for i in range(n):
    print(ans[i+1])

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import deque
import sys

sys.setrecursionlimit(200001)

N = int(input())

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

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

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

INF = 10**11
ans = [0]*N
dp = []###INFは空欄として扱って良い
stack = deque([])

def LISonTree(num,pre):
    ###num: 頂点番号
    ###pre: 1つ前にいた頂点番号
    p = bisect_left(dp,a[num])

    ###
    #print(p)
    ###

    if p >= len(dp):
        stack.appendleft((len(dp),INF))
        dp.append(a[num])
    else:
        stack.appendleft((p,dp[p]))
        dp[p] = a[num]
        
    
    q = bisect_left(dp,INF)
    ans[num] = q

    ###
    #print(num,'dp',dp)
    #print(num,'ans',ans)
    ###

    for x in graph[num]:
        if x == pre:
            continue
        LISonTree(x,num)
    
    changed_p, changed_v = stack.popleft()

    dp[changed_p] = changed_v

    ###
    #print(num,'dp',dp)
    ###

LISonTree(0,-1)
#print(ans)

for y in ans:
    print(y)

Submission status: Accepted

Solution code:
import bisect
I = [int(_) for _ in open(0).read().split()]
N = I[0]
A = [0] + I[1:1 + N]
U = [0] + I[1 + N::2]
V = [1] + I[2 + N::2]
G = [set() for _ in range(N + 1)]
for u, v in zip(U, V):
    G[u].add(v)
    G[v].add(u)
ans = [10**10] * (N + 1)
stack = [(0, 1, 1, A[1], 0)]
dp = [-10 ** 10] + [10 ** 10] * N
while stack:
    i, j, p, q, d = stack.pop()
    if d:
        dp[p] = q
        continue
    stack += [(j, i, p, dp[p], 1)]
    dp[p] = q
    ans[j] = bisect.bisect_left(dp, 10 ** 10) - 1
    while G[j]:
        k = G[j].pop()
        if i == k:
            continue
        q = A[k]
        p = bisect.bisect_left(dp, q)
        stack += [(j, k, p, q, 0)]
print(*ans[1:], sep='\n')

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def to_undirected(G):
    N = len(G)
    G = np.vstack((G, G))
    G[N:, 0] = G[:N, 1]
    G[N:, 1] = G[:N, 0]
    ind = G[:, 0].argsort()
    return G[ind]

def euler_tour(N, G, ind, root):
    parent = np.zeros(1 + N, np.int64)
    tour = np.zeros(N + N, np.int64)
    st = np.empty(len(G) + 10, np.int64)
    p = 0

    def add(v):
        nonlocal p
        st[p] = v
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return st[p]

    add(-root)
    add(root)
    n = 0
    while p:
        v = pop()
        tour[n] = v
        n += 1
        if v > 0:
            for i in range(ind[v - 1], ind[v]):
                w = G[i, 1]
                if w == parent[v]:
                    continue
                add(-w)
                add(w)
                parent[w] = v
    return tour, parent

def main(N, A, G):
    G = to_undirected(G)
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    tour, parent = euler_tour(N, G, ind, 1)
    INF = 1 << 60
    reverse = np.empty((N + 1, 2), np.int64)
    dp = np.full(N + 1, INF, np.int64)
    ans = np.empty(N + 1, np.int64)
    for v in tour:
        if v > 0:
            i = np.searchsorted(dp, A[v])
            reverse[v] = i, dp[i]
            dp[i] = A[v]
            ans[v] = np.searchsorted(dp, INF)
        else:
            v = -v
            i, x = reverse[v]
            dp[i] = x
    return ans[1:]

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    to_undirected = cc_export(to_undirected, (i8[:, :], ))
    euler_tour = cc_export(euler_tour, (i8, i8[:, :], i8[:], i8)) 
    main = cc_export(main, (i8, i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N = int(readline())
A = np.array([0] + readline().split(), np.int64)
G = np.array(read().split(), np.int64).reshape(-1, 2)

ans = main(N, A, G)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8
from numba.types import Omitted

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit((i8[:, :], ), cache=True)
def to_undirected(G):
    N = len(G)
    G = np.vstack((G, G))
    G[N:, 0] = G[:N, 1]
    G[N:, 1] = G[:N, 0]
    ind = G[:, 0].argsort()
    return G[ind]

@njit([(i8, i8[:, :], i8[:], i8), (i8, i8[:, :], i8[:], Omitted(1))],
      cache=True)
def euler_tour(N, G, ind, root=1):
    parent = np.zeros(1 + N, np.int64)
    tour = np.zeros(N + N, np.int64)
    st = np.empty(len(G) + 10, np.int64)
    p = 0

    def add(v):
        nonlocal p
        st[p] = v
        p += 1

    def pop():
        nonlocal p
        p -= 1
        return st[p]

    add(-root)
    add(root)
    n = 0
    while p:
        v = pop()
        tour[n] = v
        n += 1
        if v > 0:
            for i in range(ind[v - 1], ind[v]):
                w = G[i, 1]
                if w == parent[v]:
                    continue
                add(-w)
                add(w)
                parent[w] = v
    return tour, parent

@njit((i8, i8[:], i8[:, :]), cache=True)
def main(N, A, G):
    G = to_undirected(G)
    ind = np.searchsorted(G[:, 0], np.arange(N + 1), 'right')
    tour, parent = euler_tour(N, G, ind)
    INF = 1 << 60
    reverse = np.empty((N + 1, 2), np.int64)
    dp = np.full(N + 1, INF, np.int64)
    ans = np.empty(N + 1, np.int64)
    for v in tour:
        if v > 0:
            i = np.searchsorted(dp, A[v])
            reverse[v] = i, dp[i]
            dp[i] = A[v]
            ans[v] = np.searchsorted(dp, INF)
        else:
            v = -v
            i, x = reverse[v]
            dp[i] = x
    return ans[1:]

N = int(readline())
A = np.array([0] + readline().split(), np.int64)
G = np.array(read().split(), np.int64).reshape(-1, 2)

ans = main(N, A, G)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect

## a, bを無向辺として，隣接リストを作成
N = int(input())
a = [0] + list(map(int, input().split()))
al = [[] for i in range(N+1)]

for i in range(N-1):
    c, d = list(map(int, input().split()))
    al[c].append(d)
    al[d].append(c)

visited = [0 for i in range(N+1)]

LIS = [a[1]]
ans = [0 for i in range(N+1)]
ans[1] = 1

def dfs_rec(u):
    x = a[u]
    if x > LIS[-1]:
        pre_idx = len(LIS)
        pre_v = INF
        LIS.append(x)
    else:
        pre_idx = bisect.bisect_left(LIS, x)
        pre_v = LIS[pre_idx]
        LIS[bisect.bisect_left(LIS, x)] = x

    ans[u] = len(LIS)

    visited[u] = 1
    for v in al[u]:
        if visited[v] == 0:
            dfs_rec(v)

    if pre_v == INF:
        LIS.pop()
    else:
        LIS[pre_idx] = pre_v

dfs_rec(1)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[0]*n
dp=[float("inf")]*n
def f(c,d):
    h=bl(dp,a[c])
    g=dp[h]
    dp[h]=min(dp[h],a[c])
    b[c]=bl(dp,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c)
    dp[h]=g
f(0,-1)
for i in b:
    print(i)