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: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

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

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

INF = 10**9+1

#a = [~0,0]
q = [0]    # ~0=-1なのだが、とにかく0を打ち消す方向をやるよ、と言うこと。うまい。
dp = [INF]*N  # LIS
ans = [0]*N   # iにおけるLISの長さ
lis_len = 0   # 持ち回ってるLIS長さ変数。dpをsearchしても求まるけど、安易に野郎
idx = [-1]*N  # iのときの操作したIDX
old = [-1]*N  # iのときに操作する前の値。Rollbackする時に使う
prev = [-1]*N # 自分の呼び出しもと。グラフの行ってこいを抑止するため。

ss = 0
from bisect import bisect_left
while q:
  now = q.pop()
  # 普通のdfs
  if now >= 0:
    a = A[now]
    # LIS管理のdpに今回操作する対象のIDXを探索
    idx[now] = bisect_left(dp,a)
    # 操作前の値とIDXを保存する
    iv = idx[now]
    old[now] = dp[idx[now]]
    x = old[now]
    # LIS管理dpのVALUEがINFだったら、今回で長さが伸びるってこと
    if x == INF:
      lis_len += 1
    dp[iv] = a
    ans[now] = lis_len

    for nxt in G[now]:
      if nxt == prev[now]:
        continue
      prev[nxt] = now
      #q.append(~nxt)
      #q.append(nxt)
      q.append((-1)*nxt)
      q.append(nxt)
  # nowがゼロ以下なので、DPを一つRollbackする動きをする。
  else:
    #v = ~v # ビット反転だが、これで元のNOWを復元する
    now = (-1)*now
    dp[idx[now]] = old[now]
    x = dp[idx[now]] 
    if x == INF:
      lis_len -= 1
    
#print(*ans,sep="\n")
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
UV=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in UV:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
v=[0]*N
d=[10**9+1]*N
stk=[]
ans=[0]*N
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**9)
def dfs(p,l):
    i=bisect_left(d,A[p])
    stk.append((i,d[i]))
    d[i]=A[p]
    if i==l:
        l+=1
    ans[p]=l
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            dfs(n,l)
    i,x=stk.pop()
    d[i]=x
v[0]=1
dfs(0,0)
print(*ans,sep='\n')

Submission status: Accepted

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

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10**6)
    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: Accepted

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
import resource
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: Accepted

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 = []
    while True:
        #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
        hasNext = False
        for d in edges[n]:
            if not visited[d]:
                parent[d] = n
                n = d
                hasNext = True
        if not hasNext:
            if n == 1:
                n = 0
                break
            n = parent[n]
            # 巻き戻し
            index, value = stack.pop(len(stack)-1)
            if value < 0:
                lastLis.pop(index)
            else:
                lastLis[index] = value

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




main()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)



def main():
    n = int(ipt())
#    n = 2*10**5
    a = [int(i) for i in ipt().split()]
#    a = [i+1 for i in range(n)]
    way = [[] for i in range(n)]
    for i in range(n-1):
        u,v = map(int,ipt().split())
        u -= 1;v -= 1
        way[u].append(v)
        way[v].append(u)
#    way = [[i-1,i+1] for i in range(n)]
#    way[0] = [1]
#    way[n-1] = [n-2]
    ans = [0]*n
    dp = [10**18]*n
    stk = []

    def solve(ni,pi):
        ai = a[ni]
        pt = bisect.bisect_left(dp,ai)
        stk.append((pt,dp[pt]))
        dp[pt] = ai
        ans[ni] = bisect.bisect_left(dp,10**18-1)
        for i in way[ni]:
            if i == pi:
                continue
            else:
                solve(i,ni)
        pl,val = stk.pop()
        dp[pl] = val
        return None

    solve(0,-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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
    ans = [None]*(n+1)
    dfs(1)
    print("\n".join(list(map(str, ans[1:]))))

Submission status: Accepted

Solution code:
import bisect as bs
import sys

sys.setrecursionlimit(2*10**5+1)

def dfs(i, nbr, A, prv, done, history, B, ans):#深さ優先探索（再帰）
  
  j = bs.bisect_left(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: Accepted

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = list(LI())

MP = {}

MX = 10**10
LIS = [10**10]*N
RES = [1]*N
for i in range(N-1):
    a, b = LI()
    a -= 1
    b -= 1
    if not a in MP:
        MP[a] = []
    if not b in MP:
        MP[b] = []
    MP[a].append(b)
    MP[b].append(a)


def dfs(v, mp, lis, p):
    for u in mp[v]:
        if u != p:
            i = bisect.bisect_left(lis, AS[u])
            bef = lis[i]
            lis[i] = AS[u]
            longest = bisect.bisect_left(lis, MX)
            RES[u] = longest
            dfs(u, mp, lis, v)
            lis[i] = bef


LIS[0] = AS[0]
dfs(0, MP, LIS, -1)

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

Submission status: Accepted

Solution code:
# LIS on Tree

from collections import deque
import bisect
import sys
sys.setrecursionlimit(10**7)

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: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
A = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
inf = 10**9+1
dp = [inf]*n
que.append((0,-1))
chk = [False]*n
chk[0] = True
cnt = 0
ans = [1]*n

while que:
  now,d = que.pop()
  if d != -1:
    dp[now] = d
  else:
    ind = bisect_left(dp,A[now])
    que.append((ind,dp[ind]))
    dp[ind] = A[now]
    ans[now] = bisect_left(dp,inf)
    cnt += 1
    for i in g[now]:
      if not chk[i]:
        chk[i] = True
        que.append((i,-1))
  if cnt == n:
    break
        
print(*ans,sep='\n')

Submission status: Accepted

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

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
l = []

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

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni)
            
    if pi == -1:
        l.pop()
    else:
        l[pi] = pv


dfs(0)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from bisect import bisect_left

INF = 10 ** 9

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

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

ans = [0] * N
LIS = [INF] * (N+1)
rewinder = []

parent = [-1] * N
stack = [0]
while stack:
    node = stack.pop()
    for next_node in adj[node]:
        if ans[next_node] == 0:
            parent[next_node] = node
            stack.append(next_node)

    while rewinder and rewinder[-1][0] != parent[node]:
        _, index, prev_value = rewinder.pop()
        LIS[index] = prev_value
    
    index = bisect_left(LIS, As[node])
    rewinder.append((node, index, LIS[index]))
    LIS[index] = As[node]

    ans[node] = bisect_left(LIS, INF)

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

Submission status: Accepted

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


def dfs(j, parent):
    index = bisect_left(dp, a[j-1])
    old = dp[index]
    dp[index] = a[j-1]
    ans[j-1] = bisect_left(dp, INF)-1
    for child in to[j]:
        if child != parent:
            dfs(child, 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("\n".join(list(map(str, ans))))

Submission status: Accepted

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)
    dp = [INF]*(n+1)
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Accepted

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci = c[0]

        # lis処理
        if ans[ci] == 0:
            if len(lis) == 0:
                lis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if lis[-1] < A[ci - 1]:
                    lis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(lis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(lis[i])
                    lis[i] = A[ci - 1]

            ans[ci] = len(lis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if ans[n] != 0:
                continue
            s.append([n, lis])
            continue

        if memo[ci][0] == -1:
            if len(lis) >= 1:
                lis.pop()
        else:
            lis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci = c[0]

        # lis処理
        if ci not in v:
            if len(lis) == 0:
                lis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if lis[-1] < A[ci - 1]:
                    lis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(lis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(lis[i])
                    lis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(lis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, lis])
            continue

        if memo[ci][0] == -1:
            if len(lis) >= 1:
                lis.pop()
        else:
            lis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)
    memo = [[] for j in range(N + 1)]

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
                memo[ci].append(-1)
            else:
                if clis[-1] < A[ci - 1]:
                    clis.append(A[ci - 1])
                    memo[ci].append(-1)
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    memo[ci].append(i)
                    memo[ci].append(clis[i])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis])
            continue

        if memo[ci][0] == -1:
            if len(clis) >= 1:
                clis.pop()
        else:
            clis[memo[ci][0]] = memo[ci][1]

        s.pop()

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import bisect


def dfs(edge):
    insert = bisect.bisect_left(lis_array, a_array[edge - 1])
    old = lis_array[insert]
    lis_array[insert] = a_array[edge - 1]
    ans = bisect.bisect_left(lis_array, INF)
    ans_array[edge - 1] = ans
    for next_edge in node_dic[edge]:
        if use_array[next_edge - 1] == -1:
            use_array[next_edge - 1] = 1
            dfs(next_edge)
    lis_array[insert] = old


sys.setrecursionlimit(10 ** 9)
N = int(input())
a_array = list(map(int, input().split()))

node_dic = {}
for _ in range(N - 1):
    u, v = map(int, input().split())
    if u in node_dic:
        node_dic[u].append(v)
    else:
        node_dic[u] = [v]

    if v in node_dic:
        node_dic[v].append(u)
    else:
        node_dic[v] = [u]

# print(node_dic)

use_array = [-1] * N
ans_array = [0] * N

INF = 2 * 10 ** 9
lis_array = [INF] * N

use_array[0] = 1
dfs(1)
print("\n".join(map(str, ans_array)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)

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: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
from bisect import bisect_left
def resolve():
    def dfs(s, parent):
        a = A[s]
        i = bisect_left(dp, a)
        v = dp[i]
        dp[i] = a
        ans[s] = bisect_left(dp, INF)
        for to in G[s]:
            if to == parent:
                continue
            dfs(to, s)
        # 頂点sでの結果をもとに戻す
        dp[i] = v
        return


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

    INF = 10 ** 18
    dp = [INF] * N
    ans = [0] * N

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
import bisect  # 二分法


MAX_N = 200005
INF = 10**9 + 5

sys.setrecursionlimit(MAX_N)

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: Accepted

Solution code:
import sys
from collections import defaultdict
from bisect import bisect_left
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


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

INF = 10**20
l = [INF]*(N)
q = []
ans = [0]*(N+1)

def dfs(s, root):
    v = bisect_left(l, a[s-1])
    q.append((v, l[v]))
    l[v] = a[s-1]
    ans[s] = bisect_left(l, INF)

    for t in d[s]:
        if t==root:continue
        dfs(t, s)
    
    ba, bb = q.pop()
    l[ba] = bb

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

Submission status: Accepted

Solution code:
# 写経
# https://atcoder.jp/contests/abc165/submissions/12655073
from bisect import bisect_left, bisect_right
import sys

def resolve():
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    INF = float('inf') 
    N = int(input())
    As = list(map(int, input().split()))
    adjL = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        adjL[u].append(v)
        adjL[v].append(u)
    
    dp = [-INF]
    anss = [0] * N
    def dfs(vNow, vPar):
        A = As[vNow]
        if dp[-1] < A:
            dp.append(A)
            tp = 0
        else:
            i = bisect_left(dp, A)
            tp = 1
            iOld, AOld, = i, dp[i]
            dp[i] = A
        anss[vNow] = len(dp) - 1
    
        for v2 in adjL[vNow]:
            if v2 == vPar: continue
            dfs(v2, vNow)
    
        if tp == 0:
            dp.pop()
        else:
            dp[iOld] = AOld
    
    dfs(0, -1)

    print('\n'.join(map(str, anss)))
resolve()

Submission status: Accepted

Solution code:
import os
import sys
from io import BytesIO, IOBase
 
BUFSIZE = 8192
 
 
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
mod = 10**9 + 7

n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)
from collections import defaultdict
import bisect
def dfs(u):
    ans = [-1]*n # 各最長増加部分列の長さ
    stack = [u] # u: 頂点
    operation = defaultdict(list) # 行った操作
    used = [False]*n # 1回目: False 2回目: True
    dp = [float("inf")]*n
    dp[0] = a[u]
    used[u] = False
    length = 1
    operation[0] = [0, float("inf"), 0]
    ans[0] = 1
    while stack:
        # print(dp)
        u = stack[-1]
        if used[u] == False:
            used[u] = True
            idx = bisect.bisect_left(dp, a[u])
            operation[u] = [idx, dp[idx], length]
            dp[idx] = a[u]
            length = max(length, idx + 1)
            ans[u] = length
            for i in g[u]:
                if ans[i] > 0:
                    continue
                stack.append(i)
        else:
            idx, value, length = operation[u]
            dp[idx] = value
            stack.pop()
    return ans, used, dp
ans, used, dp = dfs(0)
print(*ans, sep="\n")
# print(used, dp)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)
from collections import defaultdict
import bisect
def dfs(u):
    ans = [-1]*n # 各最長増加部分列の長さ
    stack = [u] # u: 頂点
    operation = defaultdict(list) # 行った操作
    used = [False]*n # 1回目: False 2回目: True
    dp = [float("inf")]*n
    dp[0] = a[u]
    used[u] = False
    length = 1
    operation[0] = [0, float("inf"), 0]
    ans[0] = 1
    while stack:
        # print(dp)
        u = stack[-1]
        if used[u] == False:
            used[u] = True
            idx = bisect.bisect_left(dp, a[u])
            operation[u] = [idx, dp[idx], length]
            dp[idx] = a[u]
            length = max(length, idx + 1)
            ans[u] = length
            for i in g[u]:
                if ans[i] > 0:
                    continue
                stack.append(i)
        else:
            idx, value, length = operation[u]
            dp[idx] = value
            stack.pop()
    return ans, used, dp
ans, used, dp = dfs(0)
print(*ans, sep="\n")
# print(used, dp)

Submission status: Accepted

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

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

G = [[] for i in range(N)]
for i in range(N-1):
    uv = list(map(lambda x: int(x)-1, input().split()))
    G[uv[0]].append(uv[1])
    G[uv[1]].append(uv[0])

dp = [10 ** 10 for _ in range(N+1)]
dp[0] = -1
ans = [-1] * N

def dfs(v, p, max_):
    i = bisect_left(dp, a[v])
    memo = (i, dp[i])
    dp[i] = a[v]

    if i > max_:
        max_ = i
    ans[v] = max_

    for nv in G[v]:
        if nv == p:
            continue
        dfs(nv, v, max_)
    dp[memo[0]] = memo[1]

dfs(0, -1, 0)

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