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 bisect import bisect_right
from sys import setrecursionlimit

setrecursionlimit(10**8)
n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
    gr.append([])
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
ans = [0] * n
dp = [10 ** 10 for i in range(n)]
dp[0] = -10 ** 10
kek = 1
used = {0}


def dfs(v):
    global kek
    j = bisect_right(dp, A[v] - 1)
    old = -1
    if dp[j - 1] < A[v] < dp[j]:
        old = dp[j]
        dp[j] = A[v]
        if kek == j:
            for h in range(kek + 1, n + 1):
                if dp[h] == 10 ** 10:
                    kek = h
                    break
    ans[v] = kek - 1
    for u in gr[v]:
        if u not in used:
            used.add(u)
            dfs(u)
    dp[j] = old
    if kek > j and old == 10 ** 10:
        kek = j


dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_right
from sys import setrecursionlimit

setrecursionlimit(10**8)
n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
    gr.append([])
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
ans = [0] * n
dp = [10 ** 9 for i in range(n)]
dp[0] = -10 ** 9
kek = 1
used = {0}


def dfs(v):
    global kek
    j = bisect_right(dp, A[v] - 1)
    old = -1
    if dp[j - 1] < A[v] < dp[j]:
        old = dp[j]
        dp[j] = A[v]
        if kek == j:
            for h in range(kek + 1, n + 1):
                if dp[h] == 10 ** 9:
                    kek = h
                    break
    ans[v] = kek - 1
    for u in gr[v]:
        if u not in used:
            used.add(u)
            dfs(u)
    dp[j] = old
    if kek > j and old == 10 ** 9:
        kek = j


dfs(0)
print(*ans)

Submission status: Runtime Error

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


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

edges = [[] for _ in range(n)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_-1].append(to-1)
    edges[to-1].append(from_-1)


DP = [10**6] * n
DP[0] = 0
ans = [0] * n


def dfs(node):
    node = node
    num = A[node]
    lis = bisect.bisect_left(DP, num)

    prev = DP[lis]
    update = lis
    ans[node] = update
    DP[lis] = num
    for to in edges[node]:
        if not ans[to]:
            dfs(to)

    DP[lis] = prev


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

Submission status: Runtime Error

Solution code:
from bisect import bisect_right

n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
    gr.append([])
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
ans = [0] * n
dp = [10 ** 9 for i in range(n)]
dp[0] = -10 ** 9
kek = 1
used = {0}


def dfs(v):
    global kek
    j = bisect_right(dp, A[v] - 1)
    old = -1
    if dp[j - 1] < A[v] < dp[j]:
        old = dp[j]
        dp[j] = A[v]
        if kek == j:
            for h in range(kek + 1, n + 1):
                if dp[h] == 10 ** 9:
                    kek = h
                    break
    ans[v] = kek - 1
    for u in gr[v]:
        if u not in used:
            used.add(u)
            dfs(u)
    dp[j] = old
    if kek > j and old == 10 ** 9:
        kek = j


dfs(0)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
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)

dq = deque([1])
euler = [1]
visited = [False]*(N+1)

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


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

def f(v,l):
    if visited[v]:
        return
    visited[v] = True
    i = bisect.bisect(l,a[v-1])
    l[i] = a[v-1]
    lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:])

l = [inf] * (N+1)
l[0] = a[0]
f(1,l)

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

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

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

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

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

    dp_new = dp.copy()
    if idx == len(dp):
        dp_new.append(a[cur])
    else:
        dp_new[idx] = a[cur]

    ans[cur] = len(dp_new)

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

visited[0] = 1
dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:
import math
A,B,N =  map(int,input().split())
ans = set()
bef = 0
for x in range(1,N+1):
    ans.add(math.floor(A*x/B)-A*math.floor(x/B))
print(max(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)]

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

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

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

    if idx == len(dp):
        dp.append(a[v])
        ans[v] = len(dp)
        for target in g[v]:
            if visited[target] == 0:
                visited[target] = 1
                dfs(target, dp)
                dp.pop()
    else:
        old = dp[idx]
        dp[idx] = a[v]
        ans[v] = len(dp)
        for target in g[v]:
            if visited[target] == 0:
                visited[target] = 1
                dfs(target, dp)
                dp[idx] = old



visited[0] = 1
dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:


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)

    # print(tree)

    ans = [1] * N
    # dfs
    from bisect import bisect_left
    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)
                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:
N, M = map(int,input().split())
if N % 2 == 1:
    for i in range(1, M+1):
        print(*[i, N-i])
else:
    for i in range(1, M+1):
        if i == 1:
            print(*[1, N])
        else:
            print(*[i, N-i])

Submission status: Runtime Error

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

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

ans = [1]*n

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

root = 0
chi = [[] for i in range(n)]
par = [-1]*n
used = [False]*n
tank = [0]

while tank:
    q = tank.pop()
    used[q] = True
    for e in edge[q]:
        if not used[e]:
            chi[q].append(e)
            tank.append(e)
            par[e] = q

tank = [root]

idx = dict()
val = dict()
dp = [10**6]*n

eulerNum = -1

while tank:
    q = tank.pop()
    if q >= 0:
        #first time
        num = a[q]
        kk = bisect.bisect_left(dp,num)
        val[q] = dp[kk]
        idx[q] = kk
        dp[kk] = num
        ans[q] = kk+1

        eulerNum += 1
        tank.append(~q)
        for ch in chi[q]:
            tank.append(ch)
    else:
        if ~q != root:
            dp[idx[~q]] = val[~q]
            eulerNum += 1

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

Submission status: Runtime Error

Solution code:
import math
A,B,N =  map(int,input().split())
ans = set()
for x in range(1,N+1):
    cal = math.floor(A*x/B)-A*math.floor(x/B)
    if cal in ans:
        break
    else:
        ans.add(math.floor(A*x/B)-A*math.floor(x/B))
print(max(ans))

Submission status: Runtime Error

Solution code:


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)

    # print(tree)

    ans = [1] * N
    # dfs
    from bisect import bisect_left
    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)
                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__':
    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)]

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

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

def dfs(v, dp):
    idx = bisect_left(dp, a[v])
    # print(v + 1, dp, idx)
    ans[v] = idx + 1

    if idx == len(dp):
        dp.append(a[v])
        for target in g[v]:
            if visited[target] == 0:
                visited[target] = 1
                dfs(target, dp)
                dp.pop()
    else:
        old = dp[idx]
        dp[idx] = a[v]
        for target in g[v]:
            if visited[target] == 0:
                visited[target] = 1
                dfs(target, dp)
                dp[idx] = old



visited[0] = 1
dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
a = list(map(int, input().split()))
adj = [[] for _ in range(n)]
for _ in range(n-1):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

INF = 10**6
dp = [INF for _ in range(n)]
ans = [0 for _ in range(n)]

def dfs(x, p):
	ans[x] = bisect_left(dp, INF)
	for v in adj[x]:
		if v == p:
			continue
		ind = bisect_left(dp, a[v])
		pres = dp[ind]
		dp[ind] = a[v]
		dfs(v, x)
		dp[ind] = pres
	return

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

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

# sys.setrecursionlimit(100000)
input = sys.stdin.buffer.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


ans = [-1] * (2*10**5+1)

@mt
def slv(N, A, UV):
    A.insert(0, -1)
    g = [list() for _ in range(0, N+1)]
    for u, v in UV:
        g[u].append(v)
        g[v].append(u)


    def dfs(u, p, dp):
        global ans

        for v in g[u]:
            if v == p:
                continue

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            # print(u, p, v, i)
            ans[v] = i
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[1] = A[1]
    dfs(1, 0, dp)

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

    # return ans[:N]


def main():
    N = read_int()
    A = read_int_n()
    UV = [read_int_n() for _ in range(N-1)]
    (slv(N, A, UV))


if __name__ == '__main__':
    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)]

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

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

def dfs(v, dp):
    idx = bisect_left(dp, a[v])
    # print(v + 1, dp, idx)
    ans[v] = idx + 1

    dp_new = dp.copy()

    if idx == len(dp):
        dp_new.append(a[v])
    else:
        dp_new[idx] = a[v]

    for target in g[v]:
        if visited[target] == 0:
            visited[target] = 1
            dfs(target, dp_new)


visited[0] = 1
dfs(0, [])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
for i in range(m):
    print(i+1,n-i)

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

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

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

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

    dp_new = dp.copy()

    if idx == len(dp):
        dp_new.append(a[cur])
    else:
        dp_new[idx] = a[cur]

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


visited[0] = 1
ans[0] = 1
dfs(0, [a[0]])

for _ans in ans:
    print(_ans)

Submission status: Runtime Error

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

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

def LIS(arr):
    from bisect import bisect_left
    INF = 10 ** 15
    
    len_arr = len(arr)
    LIS = [INF for i in range(len_arr + 1)]
  
    for a in arr:
      LIS_i = bisect_left(LIS, a)
      LIS[LIS_i] = min(LIS[LIS_i], a)

    for i in range(len_arr + 1):
      if LIS[i] == INF:
        return i

MOD = 10 ** 9 + 7
INF = 10 ** 18

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

graph = [[] for _ in range(N + 1)]
for uv in UV:
    u, v = uv
    graph[u].append(v)
    graph[v].append(u)
#print(graph)

answer = [0] * (N + 1)
def dfs(prev, n, lst):
    answer[n] = LIS(lst)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, lst + [A[g]])

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

for a in answer[1:]:
    print(a)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecusionlimit(3* 10**5)

FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from bisect import bisect_left
def solve(N, A, graph):
    res = [None] * N
    res[0] = [A[0]]
    def dfs(node, par=-1):
        
        x = A[node]
        if par >= 0:
            i = bisect_left(res[par], x)
            res[node] = res[par][:]
            if i >= len(res[node]):
                res[node].append(x)
            else:
                res[node][i] = x

        for nei in graph[node]:
            if nei != par:
                dfs(nei, node)

    dfs(0)
    return map(len, res)

N = rri()
A = rrm()
graph = [[] for _ in xrange(N)]
for _ in xrange(N - 1):
    u, v = rrm()
    u -= 1; v -= 1
    graph[u].append(v)
    graph[v].append(u)

for x in solve(N, A, graph):
    print x

Submission status: Runtime Error

Solution code:
FAST_IO = 1
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from bisect import bisect_left
def solve(N, A, graph):
    res = [None] * N
    res[0] = [A[0]]
    def dfs(node, par=-1):
        
        x = A[node]
        if par >= 0:
            i = bisect_left(res[par], x)
            res[node] = res[par][:]
            if i >= len(res[node]):
                res[node].append(x)
            else:
                res[node][i] = x

        for nei in graph[node]:
            if nei != par:
                dfs(nei, node)

    dfs(0)
    return map(len, res)

N = rri()
A = rrm()
graph = [[] for _ in xrange(N)]
for _ in xrange(N - 1):
    u, v = rrm()
    u -= 1; v -= 1
    graph[u].append(v)
    graph[v].append(u)

for x in solve(N, A, graph):
    print x

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

sys.setrecursionlimit(300000)
import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [99999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)

Submission status: Runtime Error

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
a = na()
g = []
for i in range(n):
    g.append([])
for i in range(n-1):
    x, y = na()
    g[x-1].append(y-1)
    g[y-1].append(x-1)

import bisect
def dfs(cur, pre, g, lis, la, anss, a):
    ind = bisect.bisect_left(la, a[cur])
    old = la[ind]
    la[ind] = a[cur]
    nlis = lis + 1 if ind == lis + 1 else lis
    anss[cur] = nlis

    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g, nlis, la, anss, a)

    la[ind] = old

anss = [0] * n
la = [99999999] * (n+1)
la[0] = 0
dfs(0, -1, g, 0, la, anss, a)
for v in anss:
    print(v)