Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i.
Vertex i has an integer a_i written on it.
For every integer k from 1 through N, solve the following problem:

We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.

Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i \leq 10^9

1 \leq u_i , v_i \leq N

u_i \neq v_i

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

Output

Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

Sample Input 1

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Sample Output 1

1
2
3
3
4
4
5
2
2
3

For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.



Sample input:
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10


Sample output:
1
2
3
3
4
4
5
2
2
3

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from bisect import bisect_left
 
N = int(input())
A = list(map(int,input().split()))
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)
 
INF = 10**15
# dp = [ INF for _ in range(2*10**5+1)]
dp = [INF]*(2*10**5+1)
dp[0] = -INF
ans = [None]*(N)
 
def dfs(v, p=-1):
  i = 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 adj[v]:
    if u == p: continue
    dfs(u, v)
 
  dp[i] = old
 
dfs(0)
for i in range(N):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
import bisect
 
N = int(input())
A = list(map(int,input().split()))
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)
 
INF = 10**15
dp = [ INF for _ in range(2*10**5+1)]
dp[0] = -INF
ans = [None]*(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 adj[v]:
    if u == p: continue
    dfs(u, v)
 
  dp[i] = old
 
dfs(0)
for i in range(N):
  print(ans[i])

Submission status: Time Limit Exceeded

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


# def lis(A: list):
#     L = [A[0]]
#     for a in A[1:]:
#         if a > L[-1]:
#             # Lの末尾よりaが大きければ増加部分列を延長できる
#             L.append(a)
#         else:
#             # そうでなければ、「aより小さい最大要素の次」をaにする
#             # 該当位置は、二分探索で特定できる
#             L[bisect_left(L, a)] = a
#     return len(L)

def lis(arr):
    n = len(arr)

    # Declare the list (array) for LIS and
    # initialize LIS values for all indexes
    lis = [1] * n

    # Compute optimized LIS values in bottom up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    # Initialize maximum to 0 to get
    # the maximum of all LIS
    maximum = 0

    # Pick maximum of all LIS values
    for i in range(n):
        maximum = max(maximum, lis[i])

    return maximum


def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

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

    path = [[] for _ in range(N)]
    # G[v]: 頂点vに隣接する頂点list
    # N: 頂点数
    dist = [-1] * N
    que = deque([0])
    dist[0] = 0
    path[0].append(0)
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            path[w] = path[v] + [w]
            que.append(w)

    for i in range(N):
        print(lis([A[j] for j in path[i]]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


# def lis(A: list):
#     L = [A[0]]
#     for a in A[1:]:
#         if a > L[-1]:
#             # Lの末尾よりaが大きければ増加部分列を延長できる
#             L.append(a)
#         else:
#             # そうでなければ、「aより小さい最大要素の次」をaにする
#             # 該当位置は、二分探索で特定できる
#             L[bisect_left(L, a)] = a
#     return len(L)


def lis(arr):
    n = len(arr)

    # Declare the list (array) for LIS and
    # initialize LIS values for all indexes
    lis = [1] * n

    # Compute optimized LIS values in bottom up manner
    for i in range(1, n):
        for j in range(0, i):
            if arr[i] > arr[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    # Initialize maximum to 0 to get
    # the maximum of all LIS
    maximum = 0

    # Pick maximum of all LIS values
    for i in range(n):
        maximum = max(maximum, lis[i])

    return maximum


def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

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

    path = [[] for _ in range(N)]
    # G[v]: 頂点vに隣接する頂点list
    # N: 頂点数
    dist = [-1] * N
    que = deque([0])
    dist[0] = 0
    path[0].append(0)
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            path[w] = path[v] + [w]
            que.append(w)

    for i in range(N):
        print(lis([A[j] for j in path[i]]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)


def main():
    input = sys.stdin.buffer.readline
    N = int(input())
    A = list(map(int, input().split()))

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

    path = [[] for _ in range(N)]
    # G[v]: 頂点vに隣接する頂点list
    # N: 頂点数
    dist = [-1] * N
    que = deque([0])
    dist[0] = 0
    path[0].append(0)
    while que:
        v = que.popleft()
        d = dist[v]
        for w in G[v]:
            if dist[w] > -1:
                continue
            dist[w] = d + 1
            path[w] = path[v] + [w]
            que.append(w)

    for i in range(N):
        print(lis([A[j] for j in path[i]]))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def dfs(vertex):
  visited[vertex] = True
  if vertex != 0:
    maxlen = 0
    x = a[vertex]
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  ans[vertex] = max(L for (L, _) in table)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  table.pop()
  return
def notrecursion():
  visited[0] = True
  ans[0] = 1
  stack_nodes = [(node, 1) for node in adjacent[0]]
  while stack_nodes:
    node, depth = stack_nodes.pop()
    while len(table)>depth:
      table.pop()
    visited[node] = True
    maxlen = 0
    x = a[node]
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
    ans[node] = max(L for (L, _) in table)
    for neighbour in adjacent[node]:
      if not visited[neighbour]:
        stack_nodes.append((neighbour, depth+1))
  
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
table = [(1, a[0])]
notrecursion()
[print(value) for value in ans]

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def dfs(vertex):
  visited[vertex] = True
  if vertex != 0:
    maxlen = 0
    x = a[vertex]
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  ans[vertex] = max(L for (L, _) in table)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  table.pop()
  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
table = [(1, a[0])]
dfs(0)
[print(value) for value in ans]

Submission status: Time Limit Exceeded

Solution code:
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def dfs(vertex):
  visited[vertex] = True
  node_sequence.append(a[vertex])
  ans[vertex] = longest_subsequence(node_sequence)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  node_sequence.pop()
  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)
node_sequence = list()
visited = [False]*n
ans = [0]*n
dfs(0)
[print(value) for value in ans]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def dfs(vertex):
  visited[vertex] = True
  node_sequence.append(a[vertex])
  ans[vertex] = longest_subsequence(node_sequence)
  for node in adjacent[vertex]:
    if not visited[node]:
      dfs(node)
  node_sequence.pop()
  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)
node_sequence = list()
visited = [False]*n
ans = [0]*n
dfs(0)
[print(value) for value in ans]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
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)
node_sequences = [[] for _ in range(n)]
visited = [False]*n
queue_nodes = deque()
queue_nodes.append((0, []))
while queue_nodes:
  (vertex, sequence) = queue_nodes.popleft()
  visited[vertex] = True
  node_sequences[vertex] = sequence + [a[vertex]]
  for node in adjacent[vertex]:
    if not visited[node]:
      queue_nodes.append((node, node_sequences[vertex]))
[print(longest_subsequence(sequence)) for sequence in node_sequences]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def BFS():
  node_sequences = [[] for _ in range(n)]
  visited = [False]*n
  queue_nodes = deque()
  queue_nodes.append((0, []))
  while queue_nodes:
    (vertex, sequence) = queue_nodes.popleft()
    visited[vertex] = True
    node_sequences[vertex] = sequence + [a[vertex]]
    for node in adjacent[vertex]:
      if not visited[node]:
        queue_nodes.append((node, node_sequences[vertex]))
  for sequence in node_sequences:
    yield sequence
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)
long_sequences = BFS()
[print(longest_subsequence(sequence)) for sequence in long_sequences]

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z < x: # strict increasing
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def BFS():
  node_sequences = [[] for _ in range(n)]
  visited = [False]*n
  queue_nodes = deque()
  queue_nodes.append((0, []))
  while queue_nodes:
    (vertex, sequence) = queue_nodes.popleft()
    visited[vertex] = True
    node_sequences[vertex] = sequence + [a[vertex]]
    for node in adjacent[vertex]:
      if not visited[node]:
        queue_nodes.append((node, node_sequences[vertex]))
  return node_sequences
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)
long_sequences = BFS()
[print(longest_subsequence(sequence)) for sequence in long_sequences]

Submission status: Time Limit Exceeded

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))
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)

d=deque([[1,[float('inf')]]])
itta=[0]*(n+1)
# lislist=[0]*(n+1)
while d:
    now,lis=d.pop()
    # print(now,lis)
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
    else:
        lis[bisect.bisect_left(lis, a[now-1])]=a[now-1]
    itta[now]=len(lis)
    for i in edge[now]:
        if itta[i]==0:
            d.append([i,lis[:]])
# print(itta)
for i in range(n):
    print(itta[i+1])

Submission status: Time Limit Exceeded

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))
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)

d=deque([[1,[float('inf')]]])
itta=[0]*(n+1)
lislist=[0]*(n+1)
while d:
    now,lis=d.pop()
    itta[now]=1
    # print(now,lis)
    if a[now-1]>lis[-1]:
        lis.append(a[now-1])
    else:
        lis[bisect.bisect_left(lis, a[now-1])]=a[now-1]
    lislist[now]=lis
    for i in edge[now]:
        if itta[i]==0:
            d.append([i,lis[:]])
# print(lislist)
for i in range(n):
    print(len(lislist[i+1]))

Submission status: Time Limit Exceeded

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)

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import queue
inf = 10**18
n = int(input())
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    u,v = u-1,v-1
    way[u].append(v)
    way[v].append(u)

def Mnsr(ni,mns):
    mnsi = mns + [inf]
    l = 0
    r = len(mns)
    while l < r:
        mid = (r-l)//2+l
        if ni < mnsi[mid]:
            r = mid
        else:
            l = mid+1

    if not mnsi[l-1] == ni:
        mnsi[l] = ni
    return mnsi

def ansfind(arr):
    l = 0
    r = len(arr)-1
    while l < r:
        mid = l + (r-l)//2
        if arr[mid] == inf:
            r = mid
        else:
            l = mid+1
    return l-1


ans = [1 for i in range(n)]
q = queue.Queue()
for i in way[0]:
    q.put((i,0,Mnsr(a[i],[0,a[0],inf])))

while not q.empty():
    i,pi,mns = q.get()
    ans[i] = ansfind(mns)
    for j in way[i]:
        if pi == j:
            continue
        q.put((j,i,Mnsr(a[j],mns)))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import queue
n = int(input())
a = list(map(int,input().split()))
way = [[] for i in range(n)]
for i in range(n-1):
    u,v = map(int,input().split())
    u,v = u-1,v-1
    way[u].append(v)
    way[v].append(u)

stst = [[] for i in range(n)]
stst[0] = [a[0]]
q = queue.Queue()
for i in way[0]:
    q.put((i,0))

while not q.empty():
    i,pi = q.get()
    for j in way[i]:
        if pi == j:
            continue
        q.put((j,i))
    stst[i] = stst[pi]+[a[i]]

def lenlis(arr):
    mns = [10**18 for i in range(len(arr)+2)]
    mns[0] = 0
    mai = 0
    for i in arr:
        for j in range(len(arr)):
            if i > mns[j]:
                if i < mns[j+1]:
                    mns[j+1] = i
                    break
            else:
                break
    return mns.index(10**18)-1

for i in stst:
    print(lenlis(i))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    edge = np.array([input().split() for _ in range(n - 1)], dtype=np.int64).T
    b = csr_matrix(([1] * (n - 1), (edge - 1)), shape=(n, n))
    s, p = shortest_path(b, directed=False, indices=0,
                         return_predecessors=True)
    for i in range(n):
        r = [a[x] for x in get_path_row(0, i, p)]
        print(LIS(r))


def LIS(l):
    from bisect import bisect_left
    dp = [l[0]]
    for i in range(len(l)):
        if l[i] > dp[-1]:
            dp.append(l[i])
        else:
            dp[bisect_left(dp, l[i])] = l[i]
    return len(dp)


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    from scipy.sparse.csgraph import shortest_path
    from scipy.sparse import csr_matrix
    import numpy as np
    n = int(input())
    a = list(map(int, input().split()))
    edge = np.array([input().split() for _ in range(n - 1)], dtype=np.int64).T
    b = csr_matrix(([1] * (n - 1), (edge - 1)), shape=(n, n))
    s, p = shortest_path(b, directed=False, indices=0,
                         return_predecessors=True)
    ans = 0
    for i in range(n):
        r = [a[x] for x in get_path_row(0, i, p)]
        print(getlength(r))


def getlength(L):
    res = 0
    N = len(L)
    dp = [1] * N
    for i in range(N):
        for j in range(i):
            if L[j] < L[i]:
                dp[i] = max(dp[i], dp[j]+1)
        res = max(res, dp[i])
    return res


def get_path_row(start, goal, pred_row):
    path = []
    i = goal
    while i != start and i >= 0:
        path.append(i)
        i = pred_row[i]
    if i < 0:
        return []
    path.append(i)
    return path[::-1]


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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 ** 9 + 7
    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] = dp.index(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: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(_) for _ in input().split()]

#print('hoge1')
connection = [[] for _ in range(N + 1)]
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    connection[u].append(v)
    connection[v].append(u)

#print('hoge2')
parent = [None] * (N + 1)
parent[0] = 0
parent[1] = 0
ret = [None] * (N + 1)
ret[0] = [(0, 0)]
stack = [1]
#print('hoge3')
while stack:
    i = stack.pop()
    for v in connection[i]:
        if ret[v] is not None:
            continue
        parent[v] = i
        stack.append(v)
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    score_it = 0
    ret[i] = []
    while score_it < len(score):
        _ = score[score_it]
        if _[0] >= A[i - 1]:
            break
        ret[i].append(_)
        value = _[1] + 1
        score_it += 1
    ret[i].append((A[i - 1], value))
    while score_it < len(score):
        _ = score[score_it]
        if _[1] > value:
            break
        score_it += 1
    ret[i] += score[score_it:]

for i in range(1, N + 1):
    print(ret[i][-1][1])
#print('ok')

Submission status: Time Limit Exceeded

Solution code:
def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    len_s1 = len(s1)
    len_s2 = len(s2)
    i1 = 0
    i2 = 0
    ret = []
    while i1 < len_s1 and i2 < len_s2:
        if ret:
            while s1[i1][1] <= ret[-1][1]:
                i1 += 1
                if i1 == len_s1:
                    break
            while s2[i2][1] <= ret[-1][1]:
                i2 += 1
                if i2 == len_s2:
                    break
        if s1[i1][0] < s2[i2][0]:
            ret.append(s1[i1])
            i1 += 1
        elif s1[i1][0] > s2[i2][0]:
            ret.append(s2[i2])
            i2 += 1
        else: # s1[i1][0] == s2[i2][0]
            if s1[i1][1] >= s2[i2][1]:
                ret.append(s1[i1])
            else:
                ret.append(s2[i2])
            i1 += 1
            i2 += 1
    while i1 < len_s1:
        if ret:
            if s1[i1][1] > ret[-1][1]:
                ret.append(s1[i1])
        else:
            ret.append(s1[i1])
        i1 += 1
    while i2 < len_s2:
        if ret:
            if s2[i2][1] > ret[-1][1]:
                ret.append(s2[i2])
        else:
            ret.append(s2[i2])
        i2 += 1
    return ret


N = int(input())
A = [int(_) for _ in input().split()]

#print('hoge1')
connection = [[] for _ in range(N + 1)]
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    connection[u].append(v)
    connection[v].append(u)

#print('hoge2')
parent = [None] * (N + 1)
parent[0] = 0
parent[1] = 0
ret = [None] * (N + 1)
ret[0] = [(0, 0, None)]
stack = [1]
#print('hoge3')
while stack:
    i = stack.pop()
    for v in connection[i]:
        if ret[v] is not None:
            continue
        parent[v] = i
        stack.append(v)
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    score_it = 0
    ret[i] = []
    while score_it < len(score):
        _ = score[score_it]
        if _[0] >= A[i - 1]:
            break
        ret[i].append(_)
        value = _[1] + 1
        score_it += 1
    ret[i].append((A[i - 1], value, None))
    while score_it < len(score):
        _ = score[score_it]
        if _[1] > value:
            break
        score_it += 1
    ret[i] += score[score_it:]

for i in range(1, N + 1):
    print(ret[i][-1][1])
#print('ok')

Submission status: Time Limit Exceeded

Solution code:
def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    len_s1 = len(s1)
    len_s2 = len(s2)
    i1 = 0
    i2 = 0
    ret = []
    while i1 < len_s1 and i2 < len_s2:
        if ret:
            while s1[i1][1] <= ret[-1][1]:
                i1 += 1
                if i1 == len_s1:
                    break
            while s2[i2][1] <= ret[-1][1]:
                i2 += 1
                if i2 == len_s2:
                    break
        if s1[i1][0] < s2[i2][0]:
            ret.append(s1[i1])
            i1 += 1
        elif s1[i1][0] > s2[i2][0]:
            ret.append(s2[i2])
            i2 += 1
        else: # s1[i1][0] == s2[i2][0]
            if s1[i1][1] >= s2[i2][1]:
                ret.append(s1[i1])
            else:
                ret.append(s2[i2])
            i1 += 1
            i2 += 1
    while i1 < len_s1:
        if ret:
            if s1[i1][1] > ret[-1][1]:
                ret.append(s1[i1])
        else:
            ret.append(s1[i1])
        i1 += 1
    while i2 < len_s2:
        if ret:
            if s2[i2][1] > ret[-1][1]:
                ret.append(s2[i2])
        else:
            ret.append(s2[i2])
        i2 += 1
    return ret


N = int(input())
A = [int(_) for _ in input().split()]

#print('hoge1')
connection = [[] for _ in range(N + 1)]
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    connection[u].append(v)
    connection[v].append(u)

#print('hoge2')
parent = [None] * (N + 1)
parent[0] = 0
parent[1] = 0
ret = [None] * (N + 1)
ret[0] = [(0, 0, None)]
stack = [1]
stack_it = 0
while stack_it < len(stack):
    i = stack[stack_it]
    stack_it += 1
    for v in connection[i]:
        if ret[v] is not None:
            continue
        parent[v] = i
        stack.append(v)
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    #print(ret[i])
    #print(ret[i][-1][1])

#print(ret)
for i in range(1, N + 1):
    print(ret[i][-1][1])
#print('ok')