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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10**7)
from pprint import pprint as pp
from pprint import pformat as pf

import math
import bisect

class Tree:
    """
    node id starts from 1
    """

    DUMMY = 0 # used as dummy_node_id and dummy_node_value

    def __init__(self, num_node, node_values):
        self.node_values = [-1] + node_values # [0] is dummy
        self.edges = [None] * (num_node + 1) # [0] is dummy, var[a] = set of links
        for i, _ in enumerate(self.edges):
            self.edges[i] = set()
        self.seq = [self.DUMMY] * num_node

        self.dp = [math.inf] * (num_node + 1)
        self.dp[0] = -1 * math.inf
        self.ans = [0] * (num_node + 1) # [0] is dummy


    def node_values(self, node_values):
        self.node_values = [-1] + node_values # [0] is dummy

    def make_edge(self, a, b):
        self.edges[a].add(b)
        self.edges[b].add(a)

    def dps(self, node_id, prev=0, depth=0):
        # process
        value = self.node_values[node_id]
        key = bisect.bisect_left(self.dp, value)
        old_value = self.dp[key]
        self.dp[key] = value
        self.ans[node_id] = max(key, self.ans[prev])
        # recursive
        for to in self.edges[node_id]:
            if to == prev:
                continue
            self.dps(to, node_id, depth + 1)
        # recursive back
        self.dp[key] = old_value

if __name__ == '__main__':
    num_node = int(input())
    node_values = list(map(int, input().split()))
    tree = Tree(num_node, node_values)
    for i in range(num_node - 1):
        frm, to = map(int, input().split())
        tree.make_edge(frm, to)
    tree.dps(1)
    for a in tree.ans[1:]:
        print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)

N=int(sys.stdin.readline().strip())
A=[None]+map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for i in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

LIS=[ float("inf") for _ in range(N+1)] 
LIS[0]=float("-inf")
ans={}  #頂点i:LISの長さ

def dfs(cur,par):
    idx=bisect_left(LIS, A[cur])
    old=LIS[idx]    #LISの更新前の値をoldに持っておく
    LIS[idx]=A[cur]
    ans[cur]=bisect_left(LIS, float("inf"))-1 #LISの長さ
    for to in al[cur]:
        if par==to: continue    #遷移先が親であれば遷移しない
        dfs(to,cur)
    LIS[idx]=old    #oldの値を戻して、LIS配列を頂点curまで遷移した時点の状態に復元する
        
dfs(1,-1)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)

N=int(sys.stdin.readline().strip())
A=[None]+map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for i in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)

LIS=[ float("inf") for _ in range(N+1)] 
LIS[0]=float("-inf")
ans={}  #頂点i:LISの長さ

def dfs(cur,par):
    idx=bisect_left(LIS, A[cur])
    old=LIS[idx]    #LISの更新前の値をoldに持っておく
    LIS[idx]=A[cur]
    ans[cur]=bisect_left(LIS, float("inf"))-1 #LISの長さ
    for to in al[cur]:
        if par==to: continue    #遷移先が親であれば、遷移しない
        dfs(to,cur)
    LIS[idx]=old    #oldの値を戻して、LIS配列を頂点curまで遷移した時点の状態に復元する
        
dfs(1,-1)

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

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
    ans=[0]*N
    l=[INF]*(N+1)
    stk=[(0,0,0)]
    while stk:
        s,a,b=stk.pop()
        if s==0:
            i=bisect_left(l,A[a])
            stk.append((1,i,l[i]))
            l[i]=A[a]
            ans[a]=bisect_left(l,INF)
            for to in G[a]:
                if ans[to]>0: continue
                stk.append((0,to,0))
        else:
            l[a]=b
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)

N=int(sys.stdin.readline().strip())
A=[None]+map(int, sys.stdin.readline().split())

al=[ [] for _ in range(N+1) ]	#隣接リスト
for i in range(N-1):
	u,v=map(int, sys.stdin.readline().split())
	al[u].append(v)
	al[v].append(u)


LIS=[ float("inf") for _ in range(N+1)] 
LIS[0]=float("-inf")
ans={}  #頂点i:LISの長さ

def dfs(cur,par):
    idx=bisect_left(LIS, A[cur])
    old=LIS[idx]
    LIS[idx]=A[cur]
    ans[cur]=bisect_left(LIS, float("inf"))-1 #LISの長さ
    for to in al[cur]:
        if par==to: continue    #遷移先が親であれば、遷移しない
        dfs(to,cur)
    LIS[idx]=old
        
dfs(1,-1)

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

Submission status: Accepted

Solution code:
def f_lis_on_tree(INF=float('inf')):
    # 参考: https://note.com/tanon_cp/n/n51ee6db8f5b2
    import sys
    sys.setrecursionlimit(10**7)
    import bisect
    N = int(input())
    A = [0] + [int(i) for i in input().split()]  # 以下、1-origin で考える
    Edges = [[int(i) for i in input().split()] for j in range(N - 1)]

    graph = [[] for _ in range(N + 1)]
    for a, b in Edges:
        graph[a].append(b)
        graph[b].append(a)

    ans = [0] * (N + 1)
    visited = [False] * (N + 1)
    visited[1] = True  # 根は訪問済
    lis = [INF] * (N + 1)
    changes = []

    def dfs(v):
        # 行きがけの処理
        # LIS の更新する場所を二分探索で求める
        pos = bisect.bisect_left(lis, A[v])
        changes.append((pos, lis[pos]))  # 更新した要素とその値を記録しておく
        lis[pos] = A[v]
        ans[v] = bisect.bisect_left(lis, INF)  # INF が現れるまでの要素数が v での解

        # 次の頂点へ
        for child in graph[v]:
            if not visited[child]:
                visited[child] = True
                dfs(child)

        # 帰りがけの処理 (頂点 v で更新した LIS の値を復元)
        pos, val = changes.pop()
        lis[pos] = val

    dfs(1)
    return ' '.join(map(str, ans[1:]))

print(f_lis_on_tree())

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n):
    """answerのリストを更新してからdfsして、oldで戻す"""
    i = bisect_left(dp, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        i = bisect_left(dp, A[c])
        old = dp[i]
        dp[i] = A[c]
        dfs(c)
        dp[i] = old

dp = [INF] * (N+1)
dp[0] = A[1]
dfs(1)
for a in answer[1:]:
    print(a)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(dp, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        i = bisect_left(dp, A[c])
        old = dp[i]
        dp[i] = A[c]
        dfs(c)
        dp[i] = old

dp = [INF] * (N+1)
dp[0] = A[1]
dfs(1)
for a in answer[1:]:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.buffer.readline
from bisect import bisect_left
n=int(input())
*a,=map(int,input().split())
dp=[float("inf")]*n
con=[[] for _ in range(n)]
for _ in range(n-1):
	s,t=map(int,input().split())
	con[s-1].append(t-1)
	con[t-1].append(s-1)

ans=[0]*n
def dfs(cur,pre):
	idx=bisect_left(dp,a[cur])
	bef=dp[idx]
	dp[idx]=min(bef,a[cur])
	ans[cur]=bisect_left(dp,float("inf"))
	for nxt in con[cur]:
		if pre!=nxt:
			dfs(nxt,cur)
	dp[idx]=bef
dfs(0,-1)
print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    used=[False]*N
    ans=[0]*N
    dp=[INF]*(N+1)
    dp[0]=0
    dpdp=[]
    prev_l=1
    def dfs(v,l):
        used[v]=True
        index=bisect_right(dp,a[v]-1,hi=l)
        dpdp=(index,dp[index])
        dp[index]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        for nv in edge[v]:
            if not used[nv]:
                i,x=dfs(nv,l+1)
                dp[i]=x
        return dpdp
    dfs(0,1)
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


n = int(input())
A = list(map(int, input().split()))
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    edges[u].append(v)
    edges[v].append(u)
INF = 10**18
ans = [INF]*n

def dfs(v, parent):
    x = bisect.bisect_left(lis, A[v])
    prev = lis[x]
    lis[x] = A[v]
    ans[v] = bisect.bisect_left(lis, INF)
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v)
    lis[x] = prev


lis = [INF]*n
dfs(0, -1)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=-1):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = -1
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current, diffs):
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, -1))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            diffs = child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val == -1:
                current.pop()
            else:
                current[index] = val


root = Tree(0)
# root.dp([], [])

current = []
diffs = []
self = root

v = bisect.bisect_left(current, self.val)
stack = [(True, root)]
while stack:
    is_start, self = stack.pop()
    if is_start:
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, -1))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            stack.append((False, child_tree))
            stack.append((True, child_tree))

            # diffs = child_tree.dp(current, diffs)
    else:
        index, val = diffs.pop()
        if val == -1:
            current.pop()
        else:
            current[index] = val

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

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    import bisect
    
    N=I()
    A=LI()
    adj=[[]for _ in range(N)]
    
    for i in range(N-1):
        u,v=MI()
        u-=1
        v-=1
        adj[u].append(v)
        adj[v].append(u)
        
    #DFSで見ていく．オイラーツアーを作っておく．更新情報をstackに積んでおき，巻き戻る時にpopしていく
    
    #非再帰オイラーツアー
    #ETにオイラーツアー を，ET1,ET2はそれぞれ開始番号と終了番号．
    #stackで管理，行きがけと帰りがけをそれぞれi,~iで表現
    
    st_ch=[]
    #(どの場所を更新したか，元々の値は何か)を持っておく
    
    
    inf=10**10
    dp=[inf]*(N+1)
    #dp[i]は長さiを取れるときの最小末尾（普通のLISと同じ持ち方）
    dp[0]=0
    
    ans=[0]*N#答えを入れとく


    def EulerTour(n, X, i0=0):
        # 隣接グラフXを消費しながら，親リストPを作りながら進む．
        #i0が根
        P = [-1] * n
        st = [~i0, i0]
        ct = -1
        ET = []
        ET1 = [0] * n
        ET2 = [0] * n
        DE = [0] * n
        de = -1
        while st:
            #頂点 i を見る
            i = st.pop()
            
            #帰り際の処理，ここを入れる場合，オイラーツアーの最後に「-1」がつくので注意
            if i < 0:
                ct += 1
                # ↓ 戻りもETに入れる場合はこれを使う
                ET.append(P[~i])#notのnot
                ET2[~i] = ct
                de -= 1
                
                #dp-rollback
                num,val=st_ch.pop()
                dp[num]=val
                
                continue
            
            #行きがけの処理
            if i >= 0:
                ET.append(i)
                ct += 1
                if ET1[i] == 0: ET1[i] = ct
                de += 1
                DE[i] = de
                
                #dp-update
                num=bisect.bisect_left(dp,A[i])
                st_ch.append((num,dp[num]))#更新情報を入れておく
                dp[num]=A[i]#更新
                
                ans_num=bisect.bisect_left(dp,inf)
                ans[i]=ans_num-1
                
                #
                
                
            for a in X[i][::-1]:
                if a != P[i]:
                    P[a] = i
                    for k in range(len(X[a])):
                        if X[a][k] == i:
                            del X[a][k]
                            break
                    st.append(~a)
                    st.append(a)
        return (ET, ET1, ET2)
    
    EulerTour(N,adj)
    for i in range(N):
        print(ans[i])
    


                    
                
        
    

main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = [0] + list(map(int, input().split()))
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

inf = 10 ** 10
lis = [inf] * (N * 2)
s = [1]
vis = [0] * (N + 1)
euler = []
while len(s):
  x = s.pop()
  if x >= 0:
    vis[x] = 1
    euler.append(x)
    for y in e[x]:
      if vis[y]: continue
      s.append(~y)
      s.append(y)
  else: euler.append(x)

rollback = []
res = [0] * (N + 1)
for x in euler:
  if x >= 0:
    y = bl(lis, a[x])
    rollback.append((y, lis[y]))
    lis[y] = a[x]
    res[x] = bl(lis, inf)
  else:
    y, v = rollback.pop()
    lis[y] = v

for r in res[1: ]: print(r)

Submission status: Accepted

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    INF = 10 ** 18
    N = int(rl())
    A = list(map(int, rl().split()))
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(lambda x: int(x) - 1, rl().split())
        graph[u].append(v)
        graph[v].append(u)
    
    ans = [-1] * N
    stack = [0]
    dp = [INF] * (N + 1)
    rewind = [(-1, -1) for _ in range(N)]
    while stack:
        node = stack.pop()
        if 0 <= node:
            idx = bisect_left(dp, A[node])
            rewind[node] = (idx, dp[idx])
            dp[idx] = A[node]
            ans[node] = bisect_left(dp, INF)
            stack.append(~node)
            for child in graph[node]:
                if ans[child] == -1:
                    stack.append(child)
        else:
            idx, val = rewind[~node]
            dp[idx] = val
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [INF] * (n + 1)
    dp[0] = -INF
    res = 0
    ans = [None] * n
    change = [None] * n
    stack = [(0, -1)]

    while stack:
        v, p = stack.pop()
        if v >= 0:
            idx = bisect_left(dp, A[v])
            change[v] = (idx, dp[idx])
            res = max(res, idx)
            ans[v] = res
            dp[idx] = A[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            idx, prev = change[v]
            dp[idx] = prev
            res = ans[p]

    print(*ans)
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [INF] * (n + 1)
    dp[0] = -INF
    res = 0
    ans = [None] * n
    change = [None] * n
    stack = [(0, -1)]

    while stack:
        v, p = stack.pop()
        if v >= 0:
            idx = bisect_left(dp, A[v])
            change[v] = (idx, dp[idx])
            res = max(res, idx)
            ans[v] = res
            dp[idx] = A[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            idx, prev = change[v]
            dp[idx] = prev
            if prev == INF:
                res -= 1

    print(*ans)
resolve()

Submission status: Accepted

Solution code:
#F
import bisect
import sys

sys.setrecursionlimit(202020)

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

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

DP = [inf]*(N+1)
stack = []
ans = [-1]*N
seen = [False]*N

#DFS
def dfs(gragh, v): #v = start
    """
    global A
    global DP
    global ans
    global stack 
    global seen
    """
    
    seen[v] = True
    ind = bisect.bisect_left(DP,A[v])
    mae = DP[ind]
    DP[ind] = A[v]
    stack.append([ind,mae])
    
    ans[v] = bisect.bisect_left(DP,inf)
    
    for next_v in gragh[v]:
        if seen[next_v]: 
            continue
        
        dfs(gragh,next_v)
        
    ind,mae = stack.pop()
    DP[ind] = mae
    
    return



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

Submission status: Accepted

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

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)]
dp = [10**10]*n
for _ in range(n-1):
    u,v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(k, p, dp):
    flag = False
    for v in edges[k]:
        if v != p:
            l = bl(dp, a[v])
            if dp[l] > a[v]:
                idx = l
                tmp = dp[l]
                dp[l] = a[v]
                flag = True
                if tmp == 10**10:
                    ans[v] = ans[k] + 1
                else:
                    ans[v] = ans[k]
            else:
                ans[v] = ans[k]
            dfs(v, k, dp)
            if flag:
                dp[idx] = tmp
                flag = False
    return 
dfs(0, -1, dp)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
import copy
import bisect

sys.setrecursionlimit(202020)

INF = 10**12
MAX_N = 202020

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

dp = [INF for _ in range(MAX_N)]
ans = [0 for _ in range(N)]

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

dp[0] = -INF
dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**6)
INF = 10**10

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

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

ans= [0 for i in range(N+1)]
depth = [-1 for n in range(N+1)]
def dfs(s, d, dp): # 頂点番号、深さ、LIS
    depth[s] = d
    idx = bisect.bisect_left(dp,A[s])
    history = dp[idx] # 巻き戻すために保存
    dp[idx] = A[s]
    ans[s] = bisect.bisect_left(dp, INF)
    for i in adj[s]:
        if depth[i]==-1:
            dfs(i, d+1, dp)
    dp[idx] = history # 探索が終わったら巻き戻す
dp = [INF] * len(A)
dfs(1, 0, dp)
for n in range(1,N+1):
    print(ans[n])

Submission status: Accepted

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

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

ans = [0 for i in range(n)]
dp = [10**10 for _ in range(n+1)]
check = [True for _ in range(n)]
def dfs(now):
    check[now] = False
    ite = bisect_left(dp, a[now])
    tmp = dp[ite]
    dp[ite] = a[now]
    ans[now] = bisect_left(dp, 10**10)
    #print(now,dp)
    for to in G[now]:
        if check[to]:
            dfs(to)
    dp[ite] = tmp

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

Submission status: Accepted

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    tree = [list() for _ in range(N)]
    for _ in range(N-1):
        u, v = [int(x) for x in input().split()]
        u -= 1
        v -= 1
        tree[u].append(v)
        tree[v].append(u)

    ans = [1] * N

    # dfs
    def dfs(u, par):
        nonlocal ans
        nonlocal dp
        pos = bisect_left(dp, A[u])
        old = dp[pos]
        dp[pos] = A[u]

        ans[u] = bisect_left(dp, float("inf")) - 1

        for v in tree[u]:
            if v == par:
                continue
            dfs(v, u)

        dp[pos] = old

    dp = [float("inf")] * (N+1)
    dp[0] = float("-inf")
    dfs(0, -1)

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


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**6)
    main()

Submission status: Accepted

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

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

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

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

INF = 10**10

depth = [-1 for n in range(N+1)]
def dfs(s, d, lis): # 頂点番号、深さ、LIS
    depth[s] = d
    idx = bisect.bisect_left(lis,A[s])
    lis[idx], lis_c = A[s], lis[idx]
    ans[s] = bisect.bisect_left(lis, INF)
    for i in adj[s]:
        if depth[i]==-1:
            dfs(i, d+1, lis)
    lis[idx] = lis_c
lis = [INF] * len(A)
dfs(1, 0, lis)
for n in range(1,N+1):
    print(ans[n])

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from itertools import combinations_with_replacement, combinations
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
A = LI()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

depth = [0] * n
def euler_tour():
    euler = []
    dq = deque([0])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                depth[v] = depth[u] + 1
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler


order = euler_tour()
ans = [1] * n
P = [0] * n
LIS = [A[0]]
pre = 0
ret = 1
for j in range(1, len(order)):
    i = order[j]
    if depth[i] > depth[pre]:
        if A[i] > LIS[-1]:
            LIS += [A[i]]
            ret += 1
            P[i] = (-1, 0)
        else:
            idx = bisect_left(LIS, A[i])
            P[i] = (idx, LIS[idx])
            LIS[idx] = A[i]
        ans[i] = ret
    else:
        idx, e = P[pre]
        if idx == -1:
            LIS.pop()
            ret -= 1
        else:
            LIS[idx] = e
    pre = i

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

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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



idle_max=10**18

stack=deque([0])
visited={0}

miti_to_0=[-1 for i in range(N)]
miti=[set() for i in range(N)]

while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            miti_to_0[p]=a
            miti[a].add(p)
            stack.append(p)

stack=[0]
visited={0}
dp=[A[0]]
decodelst=[]
dic=defaultdict(int)
dic[0]=1
while stack:
    #print(dp)
    #print(decodelst)
    a=stack.pop()
    if miti[a]:
        p=miti[a].pop()

        if A[p]>dp[-1]:

            decodelst.append([len(dp),A[p],-1])
            dp.append(A[p])
            dic[p]=len(dp)


        else:
            i=bisect_left(dp,A[p])
            decodelst.append([i,A[p],dp[i]])
            dp[i]=A[p]
            dic[p]=len(dp)
        stack.append(p)
    else:
        if miti_to_0[a]==-1:
            break
        i,p,f=decodelst.pop()
        if f==-1:
            dp.pop()
        else:
            dp[i]=f
        stack.append(miti_to_0[a])
for i in range(N):
    print(dic[i])