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:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

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

lis=[a[0]]
stack=[]
ans=[1]*n
def dfs(cur,p=-1):
  for nx in G[cur]:
    if nx==p:continue
    idx=bisect_left(lis,a[nx])
    if idx==len(lis):
      stack.append((idx,-1))
      lis.append(a[nx])
    else:
      stack.append((idx,lis[idx]))
      lis[idx]=a[nx]
    
    ans[nx]=len(lis)

    dfs(nx,cur)

    idx,v=stack.pop()
    if v<0:
      lis.pop()
    else:
      lis[idx]=v

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

Submission status: Accepted

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

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

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    idx=bisect_left(dp,a[i])
    bef=dp[idx]
    dp[idx]=a[i]
    ans[i]=bisect_left(dp,10**18)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[idx]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
from bisect import bisect_left
INF=10**18
def dfs(v,p,max_):
    b=bisect_left(dp,a[v])
    memo=(b,dp[b])
    dp[b]=a[v]
    if b>max_:
        max_=b
    ans[v]=max_
    for nv in G[v]:
        if nv==p:
            continue
        dfs(nv,v,max_)
    dp[memo[0]]=memo[1]

N=int(input())
a=list(map(int,input().split()))
G=[[] for i in range(N)]
for i in range(N-1):
    u,v=map(lambda x:int(x)-1,input().split())
    G[u].append(v)
    G[v].append(u)
dp=[INF]*(N+1)
dp[0]=-1
ans=[-1]*N
dfs(0,-1,0)
print(*ans,sep='\n')

Submission status: Accepted

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

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    visited = set()

    def dfs(v):
        visited.add(v)

        j = bisect.bisect_left(dp, A[v])
        before_val = dp[j]
        dp[j] = A[v]

        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[j] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
def main():
    input = sys.stdin.readline
    N = int(input())
    *A, = map(int, input().split())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        u, v = u - 1, v - 1
        G[u].append(v)
        G[v].append(u)

    INF = 10**10
    tbl = [INF] * N
    stk = [(0, 0)]
    ans = [0] * N
    mx = -1
    while stk:
        s, a = stk.pop()
        if s == 0:
            v = a
            i = bisect_left(tbl, A[v])
            mx = max(mx, i)
            ans[v] = mx + 1
            stk.append((1, (i, tbl[i])))
            tbl[i] = A[v]
            for to in G[v]:
                if ans[to] > 0: continue
                stk.append((0, to))
        else:
            idx, val = a
            tbl[idx] = val
            if val == INF: mx = idx - 1
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

dp = [INF] * (N + 10)
ans = [0] * N
root = 0


def dfs(v, p):
    i = bisect.bisect_left(dp, A[v])
    prev = dp[i]
    dp[i] = A[v]
    ans[v] = bisect.bisect_left(dp, INF)
    for u in graph[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = prev


dfs(root, None)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import bisect
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

dp = [INF] * (N + 10)
ans = [0] * N
root = 0


def dfs(v, p):
    i = bisect.bisect_left(dp, A[v])
    prev = dp[i]
    dp[i] = A[v]
    ans[v] = bisect.bisect_left(dp, INF)
    # print(dp)
    for u in graph[v]:
        if u == p:
            continue
        dfs(u, v)
    assert dp[i] <= prev
    dp[i] = prev
    # print(dp)


dfs(root, None)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(dp, value)
  previous = dp[j]
  if dp[j-1] != value: # strict increasing
    dp[j] = value
  ans[vertex] = bisect_left(dp, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  dp[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
dp = [float("inf") for _ in range(n+1)]
dp[0] = float("-inf")
dfs(0)
[print(value) for value in ans]

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
from bisect import bisect, bisect_left
def longest_subsequence(sequence):
  subsequence = [float("inf") for _ in range(len(sequence)+1)]
  subsequence[0] = float("-inf")
  for value in sequence:
    j = bisect(subsequence, value)
    if subsequence[j-1] != value: # strict increasing
      subsequence[j] = value
  return bisect_left(dp, float("inf"))-1
# print(longest_subsequence([9, 13, 2, 10, 4, 13, 11, 13]))
# sys.exit()
def dfs(vertex):
  visited[vertex] = True
  value = a[vertex]
  j = bisect(subsequence, value)
  previous = subsequence[j]
  if subsequence[j-1] != value: # strict increasing
    subsequence[j] = value
  ans[vertex] = bisect_left(subsequence, float("inf"))-1
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  subsequence[j] = previous
  return
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
visited = [False]*n
ans = [0]*n
subsequence = [float("inf") for _ in range(n+1)]
subsequence[0] = float("-inf")
dfs(0)
[print(value) for value in ans]

Submission status: Accepted

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

from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)


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

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

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

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

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

    dfs(0, 0)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def read_ints(): return list(map(int, read().split()))


def read_a_int(): return int(read())


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
U, V = read_col(N - 1)
U = mina(*U)
V = mina(*V)
tree = defaultdict(lambda: [])
for u, v in zip(U, V):
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x): return int(x) - 1


def read_ints(tozero=False):
    if tozero == False:
        return list(map(int, read().split()))
    else:
        return list(map(mina1, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=None):
    ret = map(int, read().split())
    if mina == None:
        return list(ret)
    else:
        return list(map(mina1, ret))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=1)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=None):
    ret = map(int, read().split())
    if mina == None:
        return list(ret)
    else:
        return list(map(lambda x: x - 1, ret))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=1)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=None):
    ret = map(int, read().split())
    if mina == None:
        return list(ret)
    else:
        return list(map(lambda x: x - mina, ret))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=1)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=False):
    if mina:
        return list(map(mina1, read().split()))
    else:
        return list(map(int, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right
from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    a = A[now]
    # LISの更新
    idx = bisect_left(LIS, a)
    is_append = False
    if idx == len(LIS):
        LIS.append(a)
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = a  # aに更新

    ans[now] = len(LIS)  # 答えを記録
    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)

    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

Solution code:
# 木によってLISを作り、dfsで抜けるときにLISをその前の状態まで復元する

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina1(x):
    return int(x) - 1


def read_ints(mina=False):
    if mina:
        return list(map(mina1, read().split()))
    else:
        return list(map(int, read().split()))


def read_a_int():
    return int(read())


from bisect import bisect_left, bisect_right

####################
# dp = []
# for a in A:
#     print(dp)
#     idx = bisect_left(dp, a)  # 初めて真に大きい要素になるidx
#     if idx == len(dp):
#         dp.append(a)
#     else:
#         dp[idx] = a  # aに更新
# print(dp)
# print(len(dp))
####################

from collections import defaultdict
N = read_a_int()
A = read_ints()
tree = defaultdict(lambda: [])
for _ in ra(N - 1):
    u, v = read_ints(mina=True)
    tree[u].append(v)
    tree[v].append(u)

LIS = []
ans = [0] * N  # 各ノードのlen(LIS)を記録


def dfs(now, p):  # 現在のノード、親
    # 終了条件# 子が無いとき

    # LISの更新
    idx = bisect_left(LIS, A[now])
    is_append = False
    if idx == len(LIS):
        LIS.append(A[now])
        is_append = True
    else:
        old = LIS[idx]   # なんの値だったか持っておく
        LIS[idx] = A[now]  # aに更新
    ans[now] = len(LIS)  # 答えを記録

    # 次のノードを探索
    for to in tree[now]:
        if to == p:
            continue
        dfs(to, now)
    # 抜けるときにLISを復元
    if is_append:
        del LIS[idx]
    else:
        LIS[idx] = old


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

Submission status: Accepted

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

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

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

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys

input = sys.stdin.buffer.readline

n = int(input())
A = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[v].append(u)
    graph[u].append(v)

start = 1

stack = [1]
par = [-1] * (n + 1)
ans = [0] * (n + 1)
used = [False] * (n + 1)
infi = 10 ** 20
LIS = [infi] * (n + 1)
LIS[0] = -infi
position = [(-1, -1)] * (n + 1)


def hantei(val, L):
    pos = bisect_left(L, val)
    pre = L[pos]
    L[pos] = val
    cnt = bisect_left(L, infi)
    return L, pos, pre, cnt


while stack:
    v = stack[-1]
    if not used[v]:
        LIS, pos, pre, cnt = hantei(A[v], LIS)
        position[v] = (pos, pre)
        ans[v] = cnt - 1
    used[v] = True
    if not graph[v]:
        _ = stack.pop()
        basho, atai = position[v]
        LIS[basho] = atai
        continue
    u = graph[v].pop()
    if u == par[v]:
        continue
    par[u] = v
    stack.append(u)

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

n = int(input())
A = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    graph[v].append(u)
    graph[u].append(v)

start = 1

stack = [1]
par = [-1] * (n + 1)
ans = [0] * (n + 1)
used = [False] * (n + 1)
infi = 10 ** 20
LIS = [infi] * (n + 1)
LIS[0] = -infi
position = [(-1, -1)] * (n + 1)


def hantei(val, L):
    pos = bisect_left(L, val)
    pre = L[pos]
    L[pos] = val
    cnt = bisect_left(L, infi)
    return L, pos, pre, cnt


while stack:
    v = stack[-1]
    if not used[v]:
        LIS, pos, pre, cnt = hantei(A[v], LIS)
        position[v] = (pos, pre)
        ans[v] = cnt - 1
    used[v] = True
    if not graph[v]:
        _ = stack.pop()
        basho, atai = position[v]
        LIS[basho] = atai
        continue
    u = graph[v].pop()
    if u == par[v]:
        continue
    par[u] = v
    stack.append(u)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

dp = [inf]*n
ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(s, p, dp, num):
    for u in edges[s]:
        flag = False
        if u == p:
            continue
        if ans[u] != None:
            continue
        r = bl(dp, a[u])
        tmp = dp[r]
        if dp[r] == inf:
            num += 1
            flag = True
        ans[u] = num
        dp[r] = min(dp[r], a[u])
        dfs(u, s, dp, num)
        dp[r] = tmp
        if flag:
            num -= 1
    return
dfs(0, -1, dp, 1)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

dp = [inf]*n
ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(s, p, dp, num):
    for u in edges[s]:
        flag = False
        if u == p:
            continue
        r = bl(dp, a[u])
        tmp = dp[r]
        if dp[r] == inf:
            num += 1
            flag = True
        ans[u] = num
        dp[r] = min(dp[r], a[u])
        dfs(u, s, dp, num)
        dp[r] = tmp
        if flag:
            num -= 1
    return
dfs(0, -1, dp, 1)

for i in ans:
    print(i)

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)


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

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

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

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

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

    dfs(0, 0)

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


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

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

    return center


if __name__ == "__main__":
    main()

Submission status: Accepted

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

sys.setrecursionlimit(10**6)


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

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

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

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

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

    dfs(0, 0)

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


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

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

    return center


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10**6)
N,*L = map(int, open(0).read().split())
A = [0]+L[:N]
dic = [[] for i in range(N+1)]
INF = 10**20
dp = [INF]*N
ans = [0]*(N+1)
for u,v in zip(*[iter(L[N:])]*2):
  dic[u].append(v)
  dic[v].append(u)
def dfs(v,p):
  i = bisect_left(dp,A[v])
  old = dp[i]
  dp[i] = A[v]
  ans[v] = bisect_left(dp,INF)
  for u in dic[v]:
    if u==p:
      continue
    dfs(u,v)
  dp[i] = old
dfs(1,-1)
for i in range(1,N+1):
  print(ans[i])

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
from bisect import bisect_left

setrecursionlimit(10 ** 6)
INF = float("inf")

N, *I = map(int, open(0).read().split())
A, UV = I[:N], I[N:]

E = [[] for _ in range(N + 1)]
for u, v in zip(*[iter(UV)] * 2):
    E[u - 1].append(v - 1)
    E[v - 1].append(u - 1)

dp = [INF] * N
ans = [0] * N
def dfs(cur, visited):
    idx = bisect_left(dp, A[cur])
    pre = dp[idx]
    dp[idx] = A[cur]
    ans[cur] = bisect_left(dp, INF)
    for c in E[cur]:
        if c != visited:
            dfs(c, cur)
    dp[idx] = pre

dfs(0, -1)
for a in ans:
    print(a)