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: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # f([3, 5, 2, 4, 6])
    N = int(input())
    A = [int(a) for a in input().split()]
    uv = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    uv = [
        sorted(a) for a in uv
    ]
    # print(uv)

    notleaf = set()
    parent_table = dict()

    for u, v in uv:
        parent_table[v] = u
        notleaf.add(u)

    result = dict()
    result[1] = [1]

    def f(path):
        if path[-1] in result:
            return
        f(path[:-1])

        DP = result[path[-2]]

        maxindex = len(DP) - 1

        ind = path[-1]
        elem = A[ind - 1]
        for j in range(maxindex, -1, -1):
            if DP[j] < elem:
                if len(DP) == j + 1:
                    result[ind] = DP + [elem]
                    return
                if elem < DP[j + 1]:
                    DDD = [a for a in DP]
                    DDD[j + 1] = elem
                    result[ind] = DDD
                    return
        result[ind] = [a for a in DP]

    def get_path(index):
        if index == 1:
            return [1]
        return get_path(parent_table[index]) + [index]

    for i in range(1, N + 1):
        if i in notleaf:
            continue
        p = get_path(i)
        # f(p)
    # for i in range(N):
    #     print(len(result[i+1] or [] ))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

lis = [float('inf')]*n
ans = [0]*n

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:
            continue
        dfs(to, now)
    lis[idx] = tmp

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

Submission status: Runtime Error

Solution code:
import bisect

def dfs(v):
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(dp,arr[u])
      changes.append((pos,dp[pos]))
      dp[pos]=arr[u]
      ans[u]=bisect.bisect_left(dp,10**18)
      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)
ans[1]=1
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)]
dp[0]=1
changes=[(0,1)]
dfs(1)
for i in range(1,n+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # f([3, 5, 2, 4, 6])
    N = int(input())
    A = [int(a) for a in input().split()]
    uv = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    uv = [
        sorted(a) for a in uv
    ]
    # print(uv)

    notleaf = set()
    parent_table = dict()

    for u, v in uv:
        parent_table[v] = u
        notleaf.add(u)

    result = dict()
    result[1] = [1]

    def f(path):
        if path[-1] in result:
            return
        f(path[:-1])

        DP = result[path[-2]]

        maxindex = len(DP) - 1

        ind = path[-1]
        elem = A[ind - 1]
        for j in range(maxindex, -1, -1):
            if DP[j] < elem:
                if len(DP) == j + 1:
                    result[ind] = DP + [elem]
                    return
                if elem < DP[j + 1]:
                    DDD = [a for a in DP]
                    DDD[j + 1] = elem
                    result[ind] = DDD
                    return
        result[ind] = [a for a in DP]

    def get_path(index):
        if index == 1:
            return [1]
        return get_path(parent_table[index]) + [index]

    for i in range(1, N + 1):
        if i in notleaf:
            continue
        p = get_path(i)
        f(p)
    # for i in range(N):
    #     print(len(result[i+1] or [] ))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect

def dfs(v):
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(dp,arr[u])
      changes.append((pos,dp[pos]))
      dp[pos]=arr[u]
      dfs(u)
  ans[v]=bisect.bisect_left(dp,10**18)
  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)]
dp[0]=1
changes=[(0,1)]
dfs(1)
for i in range(1,n+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
from bisect import bisect_left

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

lis = [float('inf')]*(n+5)
ans = [0]*n

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:continue
        dfs(to, now)
    lis[idx] = tmp

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

Submission status: Runtime Error

Solution code:
from bisect import bisect_left


def solve(n, a_list, uv_list):
    res = [0] * n
    tree = [[] for _ in range(n)]
    for u, v in uv_list:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    # euler tour
    visited = [0] * n
    parent = [-1] * n
    tour = [0]
    p = 0
    while True:
        visited[p] = 1
        r = parent[p]
        while len(tree[p]):
            q = tree[p].pop()
            if visited[q] == 0:
                parent[q] = p
                r = q
                break
        if r == -1:
            break
        p = r
        tour.append(p)
    assert len(tour) == 2 * n - 1

    # tree DP
    dp = [10 ** 9 + i for i in range(n)]
    dp[0] = 0
    re_visited = [0] * n
    callbacks = []
    for p in tour:
        if re_visited[p] == 0:
            re_visited[p] = 1
            ind = bisect_left(dp, a_list[p])
            callbacks.append((ind, dp[ind]))
            dp[ind] = a_list[p]
            res[p] = ind
        else:
            ind, v = callbacks.pop()
            dp[ind] = v
        # print(dp)

    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    uv_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, a_list, uv_list)
    for r in res:
        print(r)


def test():
    assert solve(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]]
                 ) == [1, 2, 3, 3, 4, 4, 5, 2, 2, 3]


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]

import sys
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
g = defaultdict(list)
for i in range(n - 1):
    u = uv[i][0] - 1
    v = uv[i][1] - 1
    g[u].append(v)
    g[v].append(u)

from bisect import bisect_left
ans = [0] * n
visited = [0] * n

def dfs(cur):
    visited[cur] = 1
    idx = bisect_left(dp, a[cur])
    #print(cur, dp, idx)

    if idx == len(dp):
        old = float('inf')
        dp.append(a[cur])
    else:
        old = dp[idx]
        dp[idx] = a[cur]

    ans[cur] = len(dp)

    for target in g[cur]:
        if visited[target] == 0:
            dfs(target)

            if old == float('inf'):
                dp.pop()
            else:
                dp[idx] = old

dp = []
dfs(0)

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:
n = int(input())
a = list(map(int, input().split()))
uv = [list(map(int, input().split())) for _ in range(n - 1)]

import sys
sys.setrecursionlimit(10 ** 7)

from collections import defaultdict
g = defaultdict(list)
for i in range(n - 1):
    u = uv[i][0] - 1
    v = uv[i][1] - 1
    g[u].append(v)
    g[v].append(u)

from bisect import bisect_left
ans = [0] * n
visited = [0] * n

def dfs(cur, dp):
    visited[cur] = 1
    idx = bisect_left(dp, a[cur])
    #print(cur, dp, idx)

    if idx == len(dp):
        old = float('inf')
        dp.append(a[cur])
    else:
        old = dp[idx]
        dp[idx] = a[cur]

    ans[cur] = len(dp)

    for target in g[cur]:
        if visited[target] == 0:
            dfs(target, dp)

            if old == float('inf'):
                dp.pop()
            else:
                dp[idx] = old

dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left


def solve(n, a_list, uv_list):
    res = [0] * n
    tree = [[] for _ in range(n)]
    for u, v in uv_list:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    # euler tour
    visited = [0] * n
    parent = [-1] * n
    tour = [0]
    p = 0
    while True:
        visited[p] = 1
        r = parent[p]
        while len(tree[p]):
            q = tree[p].pop()
            if visited[q] == 0:
                parent[q] = p
                r = q
                break
        if r == -1:
            break
        p = r
        tour.append(p)

    # tree DP
    dp = [10 ** 9 + i for i in range(n)]
    dp[0] = 0
    re_visited = [0] * n
    callbacks = []
    for p in tour:
        if re_visited[p] == 0:
            re_visited[p] = 1
            ind = bisect_left(dp, a_list[p])
            callbacks.append((ind, dp[ind]))
            dp[ind] = a_list[p]
            res[p] = ind
        else:
            ind, v = callbacks.pop()
            dp[ind] = v
        # print(dp)

    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    uv_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, a_list, uv_list)
    for r in res:
        print(r)


def test():
    assert solve(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]]
                 ) == [1, 2, 3, 3, 4, 4, 5, 2, 2, 3]


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # f([3, 5, 2, 4, 6])
    N = int(input())
    A = [int(a) for a in input().split()]
    uv = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    uv = [
        sorted(a) for a in uv
    ]
    # print(uv)

    notleaf = set()
    parent_table = dict()

    for u, v in uv:
        parent_table[v] = u
        notleaf.add(u)

    result = dict()
    result[1] = [1]

    def f(path):
        if path[-1] in result:
            return
        f(path[:-1])

        DP = result[path[-2]]

        maxindex = len(DP) - 1

        ind = path[-1]
        elem = A[ind - 1]
        for j in range(maxindex, -1, -1):
            if DP[j] < elem:
                if len(DP) == j + 1:
                    result[ind] = DP + [elem]
                    return
                if elem < DP[j + 1]:
                    DDD = [a for a in DP]
                    DDD[j + 1] = elem
                    result[ind] = DDD
                    return
        result[ind] = [a for a in DP]

    def get_path(index):
        if index == 1:
            return [1]
        return get_path(parent_table[index]) + [index]

    for i in range(1, N + 1):
        if i in notleaf:
            continue
        p = get_path(i)
        f(p)
        # res = f(p)
    for i in range(N):
        print(len(result[i+1] or [] ))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # f([3, 5, 2, 4, 6])
    N = int(input())
    A = [int(a) for a in input().split()]
    uv = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    uv = [
        sorted(a) for a in uv
    ]
    # print(uv)

    notleaf = set()
    parent_table = dict()

    for u, v in uv:
        parent_table[v] = u
        notleaf.add(u)

    result = dict()
    result[1] = [1]

    def f(path):
        if path[-1] in result:
            return
        f(path[:-1])

        DP = result[path[-2]]

        maxindex = len(DP) - 1

        ind = path[-1]
        elem = A[ind - 1]
        for j in range(maxindex, -1, -1):
            if DP[j] < elem:
                if len(DP) == j + 1:
                    result[ind] = DP + [elem]
                    return
                if elem < DP[j + 1]:
                    DDD = [a for a in DP]
                    DDD[j + 1] = elem
                    result[ind] = DDD
                    return
        result[ind] = [a for a in DP]

    def get_path(index):
        if index == 1:
            return [1]
        return get_path(parent_table[index]) + [index]

    for i in range(1, N + 1):
        if i in notleaf:
            continue
        p = get_path(i)
        f(p)
        # res = f(p)
    for i in range(N):
        print(len(result[i+1]))


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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, dp: list):
        if A[u] > dp[-1]:
            dp.append(A[u])
        else:
            dp[bisect_left(dp, A[u])] = A[u]
        ans[u] = max(ans[u], len(dp))
        for v in tree[u]:
            if v != par:
                dfs(v, u, dp)
                if dp:
                    val = dp.pop()
                    if val < A[u]:
                        dp.append(A[u])

    dfs(0, -1, [A[0]])

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



if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(2*(10**5)+1)
    main()

Submission status: Runtime Error

Solution code:

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
    
ns = defaultdict(set)
for _ in range(n-1):
    u,v = [int(c) for c in input().split()]
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

from bisect import bisect_left
 
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)

ans = [None] * n

def sub(u, prev, lst, old, ind, ans):
    aa = a[u]
    if len(lst)==0 or aa > lst[-1]:
        lst.append(aa)
        old = -1
        ind = None
    else:
        ind = bisect_left(lst, aa)
        old = lst[ind]
        lst[ind] = aa
    ans[u] = len(lst)
#     print(lst)
    for v in ns[u]:
        if prev==v:
            continue
        sub(v, u, lst, old, ind, ans)
    if old==-1:
        lst.pop()
    elif old is not None:
        lst[ind] = old


sub(0, -1, [], None, None, ans)
print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
from collections import deque
from bisect import bisect_left


def solve(n, a_list, uv_list):
    res = [0] * n
    tree = [[] for _ in range(n)]
    for u, v in uv_list:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    # euler tour
    visited = [0] * n
    parent = [-1] * n
    tour = [0]
    p = 0
    while True:
        visited[p] = 1
        r = parent[p]
        for q in tree[p]:
            if visited[q] == 0:
                parent[q] = p
                r = q
                break
        if r == -1:
            break
        p = r
        tour.append(p)

    # tree DP
    dp = [10 ** 9 + i for i in range(n)]
    dp[0] = 0
    re_visited = [0] * n
    depth = -1
    callbacks = []
    for p in tour:
        if re_visited[p] == 0:
            re_visited[p] = 1
            depth += 1
            ind = bisect_left(dp, a_list[p])
            callbacks.append((ind, dp[ind]))
            dp[ind] = a_list[p]
            res[p] = ind
        else:
            ind, v = callbacks.pop()
            dp[ind] = v

    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    uv_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, a_list, uv_list)
    for r in res:
        print(r)


def test():
    assert solve(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]]
                 ) == [1, 2, 3, 3, 4, 4, 5, 2, 2, 3]


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
A = list(map(int, input().split()))
tree = [{'par': 0, 'LIS': []} for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    tree[v-1]['par'] = u - 1

tree[0]['LIS'] = [A[0]]
for i in range(1, N):
    a = A[i]
    par = tree[i]['par']
    LIS = tree[par]['LIS'][:]
    if a > LIS[-1]:
        LIS.append(a)
    else:
        LIS[bisect.bisect_left(LIS, a)] = a
    tree[i]['LIS'] = LIS[:]
for i in range(N):
    print(len(tree[i]['LIS']))

Submission status: Runtime Error

Solution code:


from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
    
ns = defaultdict(set)
for _ in range(n-1):
    u,v = [int(c) for c in input().split()]
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

from bisect import bisect_left
 
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)

ans = [None] * n

def sub(u, prev, lst, old, ind, ans):
    aa = a[u]
    if aa > lst[-1]:
        lst.append(aa)
        old = -1
        ind = None
    else:
        ind = bisect_left(lst, aa)
        old = lst[ind]
        lst[ind] = aa
    ans[u] = len(lst)
#     print(lst)
    for v in ns[u]:
        if prev==v:
            continue
        sub(v, u, lst, old, ind, ans)
    if old==-1:
        lst.pop()
    elif old is not None:
        lst[ind] = old


sub(0, -1, [a[0]], None, None, ans)
print("\n".join(map(str, ans)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    def dfs(x):
        ans[x] = bisect_left(dp, a[x])
        for e in edg[x]:
            if d[e]:
                d[e] = 0
                i = bisect_left(dp, a[e])
                p = dp[i]
                dp[i] = a[e]
                dfs(e)
                dp[i] = p
    n = II()
    a = LI()
    dp = [0] * n
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        u, v = LI_()
        edg[u].append(v)
        edg[v].append(u)
    d = [1] * n
    ans = [1] * n
    dfs(0)
    for a in ans:
        print(a)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

n=int(input())
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)
check = [False]*n
check[0] = True
li = [a[0]]
q= queue.Queue()
q.put([0,li])
ans = [0]*n
ans[0] = 1
while not q.empty():
    now,lisOrigin= q.get()
    for ne in g[now]:
        if check[ne]:
            continue
        check[ne] = True
        lis = copy.deepcopy(lisOrigin)
        if a[ne] > lis[-1]:
            lis.append(a[ne])
        else:
            lis[bisect.bisect_left(lis,a[ne])] = a[ne]
        q.put([ne,lis])
        ans[ne] = len(lis)
 
for i in range(n):
    print(ans[i])
n=int(input())
a=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)
import copy
import queue
import bisect
check = [False]*n
check[0] = True
li = [a[0]]
q= queue.Queue()
q.put([0,li])
ans = [0]*n
ans[0] = 1
while not q.empty():
    now,lisOrigin= q.get()
    for ne in g[now]:
        if check[ne]:
            continue
        check[ne] = True
        lis = copy.deepcopy(lisOrigin)
        if a[ne] > lis[-1]:
            lis.append(a[ne])
        else:
            lis[bisect.bisect_left(lis,a[ne])] = a[ne]
        q.put([ne,lis])
        ans[ne] = len(lis)

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

Submission status: Runtime Error

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

d = [-1 for _ in range(n)]

def dfs(i, s):
    d[i] = len(s)

    for to in edges[i]:
        if d[to] == -1:
            t = s.copy()
            if t[-1] < a[to]:
                t.append(a[to])
                dfs(to, t)
            else:
                t[bisect.bisect_left(t, a[to])] = a[to]
                dfs(to, t)

dfs(0, [a[0]])
for i in range(n):
    print(d[i])

Submission status: Runtime Error

Solution code:
import bisect

def dfs(v,l,tr):
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        dfs(u,l+1,tr+[arr[u]])
      elif tr[pos]==arr[u]:
        dfs(u,l,tr)
      else:
        dfs(u,l,tr[:pos]+[arr[u]]+tr[pos+1:])

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
dfs(1,1,[arr[1]])
for i in range(1,n+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_left


def dfs(v, p, links, state, ans):
    # print(v, p, state, ans)
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        b = -1
        i = bisect_left(state, aaa[u])
        if i == len(state):
            state.append(a)
        else:
            b = state[i]
            state[i] = a
        dfs(u, v, links, state, ans)
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import bisect

def dfs(v,l,tr):
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        dfs(u,l+1,tr+[arr[u]])
      elif tr[pos]==arr[u]:
        dfs(u,l,tr)
      else:
        dfs(u,l,tr[:pos]+[arr[u]]+tr[pos+1:])

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
dfs(1,1,[arr[1]])
for i in range(1,n+1):
  print(ans)

Submission status: Runtime Error

Solution code:
import bisect

def lis(lst):
    lis_lst = [lst[0]]
    for i in lst:
        if i > lis_lst[-1]:
            lis_lst.append(i)
        else:
            lis_lst[bisect.bisect_left(lis_lst, i)] = i
    return len(lis_lst)

n = int(input())

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

uv = {}
for _ in range(n-1):
    u, v = map(int, input().split())
    uv[v] = u
    
for i in range(1, n + 1):
    lst = []    
    while i != 1:
        lst.append(a[i - 1])
        i = uv[i]
    lst.append(a[0])
    lst.reverse()
    print(lis(lst))

Submission status: Runtime Error

Solution code:
from collections import deque

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

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

ans = [0] * n
ans[0] = 1
mark = [0] * n
mark[0] = a[0]
mark2 = [-1] * n
visited = [False] * n
visited[0] = True

q = deque([0])

while q:
    i = q.popleft()
    for j in g[i]:
        if visited[j]:
            continue
        if mark[i] < a[j]:
            mark[j] = a[j]
            mark2[j] = mark[i]
            ans[j] = ans[i] + 1
        else:
            if a[j] > mark2[j]:
                mark[j] = marl[i]
            ans[j] = ans[i]
        visited[j] = True
        q.append(j)

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

Submission status: Runtime Error

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)).toarray()
    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: Runtime Error

Solution code:
import bisect

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

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


ans = [0] * N
ans[0] = 1
dp = []
def dfs(node, par, dp):
  global ans
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    if idx == len(dp):
      _dp = dp.copy() + [num]
      ans[child] = idx + 1
      dfs(child, node, _dp)
    else:
      _dp = dp.copy()
      _dp[idx] = num
      ans[child] = idx + 1
      dfs(child, node, _dp)

dp = [A[0]]
dfs(0, -1, dp)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import bisect

n = int(input())
A = list(map(int,input().split()))
N = [[]for _ in range(n)]; N[0].append(-1)
Ans = [0 for i in range(n)]
A_MAX = 10**10

def delete(y,x):
    N[y].remove(x)
    for v in N[y]:
        delete(v,y)






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

  

delete(0,-1) 

def solve(next_u,L):
    A_temp = A[next_u]
    if A_temp>=L[-1]:
        L.append(A_MAX)
    
    start_index = bisect.bisect_left(L,A_temp)
    
    L = L[:start_index] + [A_temp for _ in range(len(L)-start_index)]
    
    Ans[next_u]=len(L)
    
    for v in N[next_u]:
        solve(v,L)


    
    
solve(0,[0])

for i in range(n):
    print(Ans[i]-1)

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
if n %2 == 0:
    k = 2*m+2
    for i in range(m):
        if i == 0:
            print(i+1, k)
        else:
            print(i+1, k-1-i)
else:
    for i in range(m):
        print(i+1, n-1-i)