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
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]

Submission status: Accepted

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    old = seq[pos]
    seq[pos]=a[i-1]
    ans[i-1]=bisect_left(seq,INF)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = [INF]*N
ans = [-1]*N

dfs(1,-1)
[print(i) for i in ans]

Submission status: Accepted

Solution code:
import bisect

def dfs(graph, root, A, res, lis):
    stack = [(root,)]
    while stack:
        # print(stack)
        state = stack[-1]
        del stack[-1]
        u = state[0]
        if res[u] == -1:
            a = A[u]
            p = bisect.bisect_left(lis, a)
            if p == len(lis):
                stack.append((u, -1))
                lis.append(a)
            else:
                stack.append((u, p, lis[p]))
                lis[p] = a
            res[u] = len(lis)
            for v in graph[u]:
                if res[v] == -1:
                    stack.append((v,))
        else:
            p = state[1]
            if p >= 0:
                lis[p] = state[2]
            else:
                del lis[-1]

n = int(input())
A = [int(x) for x in input().split()]
graph = [[] for i in range(n)]
for i in range(n - 1):
    u, v = [int(x) - 1 for x in input().split()]
    graph[u].append(v)
    graph[v].append(u)
res = [-1] * n
dfs(graph, 0, A, res, [])
print(*res, sep='\n')

Submission status: Accepted

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

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append((-1, 0))
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
        else:
            history.append((-2, 0))
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k[0] == -2:
            None
        elif k[0] == -1:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)

Submission status: Accepted

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

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

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

    INF = 10 ** 18    
    ans = [0] * N
    dp = [INF] * N
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        old = dp[idx]
        dp[idx] = a

        ans_idx = bisect_left(dp, INF)
        ans[now] = ans_idx

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        dp[idx] = old
    
    dfs(0, -1)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
a = list(map(int, input().split()))

result = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]
for _i in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    tree[u].append(v)
    tree[v].append(u)
INF = float('inf')
dp = [INF for _i in range(n+1)]


def dfs(p, x):
    i = bisect_left(dp, a[p])
    old = dp[i]
    dp[i] = a[p]
    result[p] = bisect_left(dp, INF)
    for j in tree[p]:
        if j != x:
            dfs(j, p)
    dp[i] = old
    

dfs(0, -1)
print(*result)

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 9)
n = int(input())
a = list(map(int, input().split()))

result = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]
for _i in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    tree[u].append(v)
    tree[v].append(u)
INF = float('inf')
dp = [INF for _i in range(n+1)]


def dfs(p, x):
    i = bisect_left(dp, a[p])
    old = dp[i]
    dp[i] = a[p]
    result[p] = bisect_left(dp, INF)
    for j in tree[p]:
        if j != x:
            dfs(j, p)
    dp[i] = old
    

dfs(0, -1)

for i in result:
    print(i)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
input=sys.stdin.buffer.readline
N=int(input())
*a,=map(int,input().split())
w=[[]for _ in range(N)]
INF=10**18
for _ in range(N-1):
  u,v=map(int,input().split())
  w[u-1].append(v-1)
  w[v-1].append(u-1)
dp=[INF]*N
ans=[0]*N

def dfs(now,pre):
  idx=bisect_left(dp,a[now])
  before=dp[idx]
  dp[idx]=min(before,a[now])
  ans[now]=bisect_left(dp,INF)
  for nxt in w[now]:
    if pre!=nxt:
      dfs(nxt,now)
  dp[idx]=before
dfs(0,-1)
print(*ans,sep='\n')

Submission status: Accepted

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

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    to = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    
    ans = [0] * N
    dp = []
    def dfs(now, pre):
        a = A[now]
        idx = bisect_left(dp, a)

        if idx == len(dp):
            old = -1
            dp.append(a)
        else:
            old = dp[idx]
            dp[idx] = a
        
        ans[now] = len(dp)

        
        for nv in to[now]:
            if nv != pre:
                dfs(nv, now)
        

        if old == -1:
            dp.pop()
        else:
            dp[idx] = old

    
    dfs(0, -1)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
from  bisect import bisect_left
input = sys.stdin.readline
INF = 1 << 30

MAXN = 200005
G = [[] for _ in range(MAXN)]
dp = [INF] * MAXN
stack = []
ans = [None] * MAXN
def dfs(v,A,p = -1):
    idx = bisect_left(dp,A[v])
    stack.append((idx,dp[idx]))
    dp[idx] = A[v]
    ans[v] = bisect_left(dp,INF)
    for e in G[v]:
        if e == p:
            continue
        dfs(e,A,v)
    idx,p = stack.pop()
    dp[idx] = p

def main():
    N = int(input())
    A = list(map(int,input().split()))
    for _ in range(N - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    dfs(0,A)
    print('\n'.join(map(str,ans[:N])))
if __name__ == '__main__':
    main()

Submission status: Accepted

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

class SegmentTree():
    f = max
    unit = 0
   
    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        #self._build(array)
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

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

B = sorted(list(set(A)))
M = len(B)
toID = {i:j for i,j  in zip(B,range(1,M + 1))}
dp = SegmentTree([0] * (M + 1))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    flag = False
    if before[v] < a:
        flag = True
        dp.update(idx,a)
    before_max = dp.query(0,M + 1)
    ans[v] = max(before_max,a)
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    if flag:
        dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Accepted

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

class SegmentTree():
    f = max
    unit = 0

    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

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

B = sorted(list(set(A)))
M = len(B)
toID = {i:j for i,j  in zip(B,range(1,M + 1))}
dp = SegmentTree([0] * (M + 1))
ans = [0] * N
before = [0] * N

def dfs(v,p = -1):
    idx = toID[A[v]]
    a = dp.query(0,idx) + 1
    before[v] = dp.query(idx,idx + 1)
    flag = False
    if before[v] < a:
        flag = True
        dp.update(idx,a)
    before_max = dp.query(0,M + 1)
    ans[v] = max(before_max,a)
    for e in G[v]:
        if e == p:
            continue
        dfs(e,v)
    if flag:
        dp.update(idx,before[v])

dfs(0)
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
def main():

    from bisect import bisect_left as bl

    n = int(input())
    a = list(map(int, input().split()))
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    ans = [0]*n
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    visited = [False]*n

    q = [0]
    lis = []
    while q:
        i = q.pop()
        ai = a[i]
        if not visited[i]:
            b = bl(lis, ai)
            if b == len(lis):
                visited[i] = "push"
                lis.append(ai)
            else:
                visited[i] = [b, lis[b]]
                lis[b] = ai
            ans[i] = len(lis)
        if not g[i]:
            if visited[i] == "push":
                lis.pop()
            else:
                lis[visited[i][0]] = visited[i][1]
        else:
            q.append(i)
            j = g[i].pop()
            g[j].remove(i)
            q.append(j)
    for i in ans:
        print(i)


main()

Submission status: Accepted

Solution code:
from collections import deque
import bisect

N=int(input())
A=list(map(int,input().split()))
ans=[0]*N
Edge=[[] for _ in range(N)]
loute=[str(0)]*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)
  
tmp=deque(str(0))
CHN=deque()
LIS=[10**18]*N
label=[False]*N
while tmp:
    T0=int(tmp[-1])
    if label[T0]:
        tmp.pop()
        pos,Val=CHN.pop()
        LIS[pos]=Val
        continue

    pos=bisect.bisect_left(LIS,A[T0])
    CHN.append((pos,LIS[pos]))
    LIS[pos]=A[T0]
    ans[T0]=bisect.bisect_left(LIS,10**18)

    if Edge[T0]:
        for i in Edge[T0]:
            if label[i]==False:
                tmp.append(i)
        label[T0]=True
    else:
        label[T0]=True
    
for i in range(N):
    print(ans[i])

Submission status: Accepted

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

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

E=[[] for i in range(N+1)]
for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

USE=[0]*(N+1)
USE[1]=1
ANS=[0]*(N+1)
DP=[]

def dfs(x):
    pos=bisect.bisect_left(DP,A[x])
    
    if pos<len(DP):
        changepos=pos
        old=DP[pos]
        
        DP[pos]=A[x]
    else:
        changepos=pos
        old=-1
        
        DP.append(A[x])

    ANS[x]=len(DP)

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            dfs(to)

    if old==-1:
        DP.pop()
    else:
        DP[changepos]=old

dfs(1)

print(*ANS[1:])

Submission status: Accepted

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

from bisect import bisect_left
from collections import deque
"""
行き ⇨ dp LIS計算とstack登録
帰り ⇨ stackをpop dp巻き戻し
"""

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


INF = 10**10
dp = []
pos = 0
ans = [0] * n
q = deque([])
def dfs(v,p):
    global pos
    # 行き
    a = As[v]
    ind = bisect_left(dp, a)
    if ind == len(dp): 
        dp.append(a)
        # 引数の1つ目はappendしたか
        q.append((True, -1, -1))
    else:
        # 更新
        tmp = dp[ind]
        dp[ind] = a
        q.append((False,ind,tmp))

    ans[v] = len(dp)
    for u in edges[v]:
        if u == p:continue
        dfs(u,v)
        # 帰り        
        isappend, ind, tmp = q.pop()
        if isappend:
            dp.pop()
        else:
            dp[ind] = tmp
        
    
dfs(0,-1)

print(*ans)

Submission status: Accepted

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)
n = int(input())
a = [0]+list(map(int,input().split()))
tree = [[] for _ in range(n+1)]
for _ in range(n-1):
  u,v = map(int,input().split())
  tree[u].append(v)
  tree[v].append(u)
#print(tree)
d = [float("inf")]*(n+1)
ans = [0]*(n+1)

def dfs(now, pre):
  i = bisect.bisect_left(d, a[now])
  tmp = d[i]
  d[i] = a[now]
  ans[now] = bisect.bisect_left(d, float("inf"))
  for nxt in tree[now]:
    if nxt == pre:
      continue
    dfs(nxt, now)
  d[i] = tmp
dfs(1,-1)

for i in ans[1:]:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
N = int(input())
A = list(map(int,input().split()))
UV = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for u,v in UV:
    u,v = u-1,v-1
    es[u].append(v)
    es[v].append(u)

from bisect import bisect_left
lis = [A[0]]
stack = []
ans = [1] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        i = bisect_left(lis, A[to])
        if i == len(lis):
            stack.append((i,-1))
            lis.append(A[to])
        else:
            stack.append((i,lis[i]))
            lis[i] = A[to]
        ans[to] = len(lis)

        dfs(to,v)

        i,a = stack.pop()
        if a < 0:
            lis.pop()
        else:
            lis[i] = a

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

Submission status: Accepted

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

def dfs(v):
    pos=bisect.bisect_left(dp,arr[v])
    changes.append((pos,dp[pos]))
    dp[pos]=arr[v]
    ans[v]=bisect.bisect_left(dp,10**18)
    for u in g[v]:
        if checked[u]==0:
            checked[u]=1
            dfs(u)
    pos,val=changes.pop()
    dp[pos]=val


n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    g[a].append(b)
    g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)]
changes=[]
dfs(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Accepted

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

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

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

rooted = [[] for _ in range(n)]
que = [(0, -1)]
while que:
    node, parent = que.pop()
    for child in graph[node]:
        if child != parent:
            rooted[node].append(child)
            # rooted[child].append(node)
            que.append((child, node))
            # print(child + 1, node + 1)

table = [float('inf')] * n
lis = [None] * n
def dfs(node, length=0):
    p = bisect.bisect_left(table, a[node])
    table[p], old = a[node], table[p]
    length = max(p + 1, length)
    for child in rooted[node]:
        dfs(child, length)
    table[p] = old
    lis[node] = length

dfs(0)
print(*map(str, lis), sep="\n")

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    from bisect import bisect_left

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

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

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

    root = 0
    stack = [root]
    visited = set()
    visited.add(root)
    done = set()
    vs = []

    ans = [0] * N
    memo = [None] * N
    memo[root] = (0, A[root])

    INF = 10 ** 10
    dp = [INF] * N

    while stack:
        now_ = stack[-1]
        if now_ in done:
            j, a = memo[now_]
            dp[j] = a
            stack.pop()
            vs.append(now_)
        else:
            for next_ in G[now_][::-1]:
                if next_ in visited:
                    continue
                visited.add(next_)
                stack.append(next_)
            done.add(now_)

            tmp = bisect_left(dp, A[now_])
            memo[now_] = (tmp, dp[tmp])
            dp[tmp] = A[now_]
            ans[now_] = bisect_left(dp, INF)

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

from bisect import bisect_left

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

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

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

root = 0
stack = [root]
visited = set()
visited.add(root)
done = set()
vs = []

ans = [0] * N
memo = [None] * N
memo[root] = (0, A[root])

INF = 10 ** 10
dp = [INF] * N

while stack:
    now_ = stack[-1]
    if now_ in done:
        j, a = memo[now_]
        dp[j] = a
        stack.pop()
        vs.append(now_)
    else:
        for next_ in G[now_][::-1]:
            if next_ in visited:
                continue
            visited.add(next_)
            stack.append(next_)
        done.add(now_)

        tmp = bisect_left(dp, A[now_])
        memo[now_] = (tmp, dp[tmp])
        dp[tmp] = A[now_]
        ans[now_] = bisect_left(dp, INF)

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

Submission status: Accepted

Solution code:
#MLE注意！0や1のケースに注意

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    n = int(input())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)] #頂点数, 場合によって変える
    for _ in range(n-1):
        c,b = map(int, input().split())
        adj[c-1].append(b-1)
        adj[b-1].append(c-1)

    # 頂点1も含む
    res = [0]*n
    res[0] = 1

    def dfs(v, par, L):
        if v != 0:
            if a[v] > L[-1]:
                temp = -1
                L.append(a[v])
            else:
                temp = bisect_left(L, a[v])
                pre = L[temp]
                L[temp] = a[v]
        res[v] = len(L)
        for nv in adj[v]:
            if nv == par:
                continue
            dfs(nv, v, L)
        if v != 0:
            if temp == -1:
                L.pop(-1)
            else:
                L[temp] = pre

    L = [a[0]]
    dfs(0, -1, L)
    for i in range(n):
        print(res[i])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)

    def euler_tour(self):
        res = []
        begin = [None for _ in range(self.n)]
        end = [None for _ in range(self.n)]
        visited = [0 for _ in range(self.n)]
        visited[self.root] = 1
        stack = [self.root]
        while stack:
            node = stack.pop()
            if node >= 0:
                res.append(node)
                stack.append(~node)
                if begin[node] is None:
                    begin[node] = len(res) - 1
                for adj in self.tree[node]:
                    if visited[adj]:
                        continue
                    visited[adj] = 1
                    stack.append(adj)
            else:
                end[~node] = len(res)
                if ~node != self.root:
                    res.append(self.parent[~node])
        return res, begin, end


from bisect import bisect_left
import sys
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)
T.setroot(0)

et, _, _ = T.euler_tour()
res = [None for _ in range(N)]
lis = []
rec = [None for _ in range(N)]
prev = None

for node in et:
    if res[node] is None:
        if not lis or A[node] > lis[-1]:
            lis.append(A[node])
        else:
            idx = bisect_left(lis, A[node])
            rec[node] = (idx, lis[idx])
            lis[idx] = A[node]
        res[node] = len(lis)

    else:
        if rec[prev] is not None:
            lis[rec[prev][0]] = rec[prev][1]
        else:
            lis.pop()

    prev = node

print('\n'.join(map(str, res)))

Submission status: Accepted

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


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


class solve:
    def __init__(self, N):
        self.ans = [0] * N
        self.DP = []

    def recur(self, i, pi=-1):
        # DPテーブルを更新し、答えを求める。
        # また、巻き戻す値を覚える。
        rev_i = bisect(self.DP, self.A[i])
        if rev_i == len(self.DP):
            self.DP.append(self.A[i])
            rev_v = None
        else:
            rev_v = self.DP[rev_i]
            self.DP[rev_i] = self.A[i]

        self.ans[i] = len(self.DP)

        for nv in self.edges[i]:
            if nv != pi:
                self.recur(nv, i)

        # 巻き戻す。.
        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


def main():
    N = int(input())
    S = solve(N)
    S.A = inpl()
    S.edges = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = inpl()
        S.edges[u - 1].append(v - 1)
        S.edges[v - 1].append(u - 1)

    S.recur(0)

    print(*S.ans, sep='\n')
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []
    var = {"last": 0}

    def dfs(curr, par):
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            if dp[i] == INF:
                var["last"] = i
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = var["last"]+1

        for child, w in g.E[curr]:
            if child == par:
                continue
            dfs(child, curr)

        c, i, v = event[-1]
        if c == curr:
            dp[i] = v
            if v == INF:
                var["last"] = i-1
            event.pop()

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

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)


if __name__ == '__main__':
    main()