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: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter


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

import sys
import bisect
input = sys.stdin.readline
n = int(input())
num = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
et = euler_tour(graph,1)
vis = [0]*(n+1)
ans = [0]*(n+1)
dp = [0]
parent = [0]*(n+1)
dc = defaultdict(int)
for i in range(len(et)):
  x = et[i]
  m = num[x-1]
  if vis[x] == 0:
    if x != 1:
      parent[x] = et[i-1]
    idx = bisect.bisect_left(dp,m)
    if idx == len(dp):
      dp.append(m)
      dc[x] = -1
    else:
      dc[x] = dp[idx]
      dp[idx] = m
    ans[x] = len(dp)-1
    vis[x] = 1
  else:
    prv = num[et[i-1]-1]
    kid = et[i-1]
    change = dc[kid]
    idx = bisect.bisect_left(dp,prv)
    if change == -1:
      dp.pop()
    else:
      dp[idx] = change
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
a = [0] + list(map(int, input().split()))
g = [[] for i in range(n+1)]
for i in range(n-1):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)


q = [(1, [a[1]])]
ans = [None]*(n+1)
ans[1] = 1
while q:
    now, now_l = q.pop()
    for next in g[now]:
        if ans[next] == None:
            if a[next] > now_l[-1]:
                q.append((next, now_l + [a[next]]))
                ans[next] = len(now_l) + 1
            else:

                now_l[bisect.bisect_left(now_l, a[next])] = a[next]
                q.append((next, now_l))
                ans[next] = len(now_l)

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

Submission status: Wrong Answer

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

from collections import defaultdict
G = defaultdict(list)

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

from bisect import bisect
ansl = [0 for i in range(n)]
dp = [[float("inf") for _ in range(n+1)] for i in range(n)]
dp[0][0] = -1
used = [0 for i in range(n)]
used[0] = 1

def dfs(pos, dp):
    idx = bisect(dp[pos], al[pos])
    dp[pos][idx] = min(al[pos], dp[pos][idx])
    ansl[pos] = max(i for i in range(n+1) if dp[pos][i] < float("inf"))
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dp[v] = dp[pos][:]
            dfs(v, dp)


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[i])

Submission status: Wrong Answer

Solution code:
import sys
import heapq


sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def dijkstra(start, n_nodes, edge, A):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    res = [0] * n_nodes
    res[0] = 1

    # 優先度キューの準備
    q = [(dist[start], start, 1, 1)]
    heapq.heapify(q)

    while q:
        # スタートから最も最短距離のものを取り出す
        d, i, cnt, M = heapq.heappop(q)

        # 記録してある情報よりも，取り出した要素に入っている距離情報の方が大きければ
        # 打ち切り．次の要素を取り出す操作に戻る
        if dist[i] < d:
            continue

        # そこから移動できる頂点を探し，最短距離が更新できるものがあれば，
        # 距離を更新して，その頂点への距離と頂点の方法を優先度キューにpush
        for cost, j in edge[i]:
            if dist[j] > dist[i] + cost:
                dist[j] = dist[i] + cost
                if A[i] < A[j]:
                    cnt_j = cnt + 1
                    if M < cnt_j:
                        M_j = cnt_j
                    else:
                        M_j = M
                else:
                    cnt_j = 1
                    M_j = M

                res[j] = M_j

                heapq.heappush(q, (dist[j], j, cnt_j, M_j))

    return res


def input():
    return sys.stdin.readline().strip()


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

    ans = dijkstra(0, N, edges, A)

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect
from sys import setrecursionlimit

setrecursionlimit(10000000)

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


res = [None]*N
dp = [float('inf') for _ in range(N)]

def rec(v, ml):
    """
    dp[l]: min tail value of increasing subsequence of length l+1
    """
    a = A[v]
    i = bisect(dp, a)
    ml += int(ml == i)
    res[v] = ml

    orig = dp[i]
    dp[i] = a
    for u in adj[v]:
        if res[u] is None:
            rec(u, ml)
    dp[i] = orig

rec(0, 0)

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

Submission status: Wrong Answer

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(1 + 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, 1 + n):
                if dp[h] == 10 ** 10:
                    kek = h
                    break
            if kek == j:
                kek = n + 1
    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: Wrong Answer

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

sys.setrecursionlimit(10 ** 7)

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 LLL(a, ls):
    INF = 10 ** 15
    
    flag = 0
    prev = 0
    indx = 0
    ls_i = bisect_left(ls, a)
    if a < ls[ls_i]:
        flag = 1
        prev = ls[ls_i]
        indx = ls_i
    ls[ls_i] = min(ls[ls_i], a)

    ls_ii = bisect_left(ls, INF)
    return ls_ii, ls, flag, prev, indx

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)

INF = 10 ** 15

LIS = [INF for i in range(N + 2)]

answer = [0] * (N + 1)
def dfs(prev, n, LIS):
    answer[n], LIS, flag, prv, indx = LLL(A[n], LIS)
    #print(n, LIS, flag, prv, indx)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, LIS)
    LIS[indx] = prv

dfs(-1, 1, LIS)

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

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 7)

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 LLL(a, ls):
    INF = 10 ** 15
    
    flag = 0
    prev = 0
    indx = 0
    ls_i = bisect_left(ls, a)
    if a < ls[ls_i]:
        flag = 1
        prev = ls[ls_i]
        indx = ls_i
    ls[ls_i] = min(ls[ls_i], a)

    for i in range(N + 1):
      if ls[i] == INF:
        return i, ls, flag, prev, indx

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)

INF = 10 ** 15

LIS = [INF for i in range(N + 1)]

answer = [0] * (N + 1)
def dfs(prev, n, LIS):
    answer[n], LIS, flag, prv, indx = LLL(A[n], LIS)
    #print(n, LIS, flag, prv, indx)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, LIS)
    LIS[indx] = prv

dfs(-1, 1, LIS)

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

Submission status: Wrong Answer

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
        # print(ans[:N+1])
        # print(u, dp)

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

            i = bisect.bisect_left(dp, A[v])
            b = dp[i]
            dp[i] = A[v]
            ans[v] = bisect.bisect_left(dp, INF) - 1
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[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: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X[x].append(y)
    X[y].append(x)

def EulerTour(n, X, i0):
    def bl(k):
        l, r = -1, n-1
        while r - l > 1:
            m = (l + r) // 2
            if L[m][-1] < k:
                l = m
            else:
                r = m
        return l + 1

    inf = 1 << 30
    P = [-1] * n
    Q = [~i0, i0]
    ANS = [0] * n
    L = [[inf] for _ in range(n)]
    I = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~i
            L[I[i]].pop()
            continue
        if i >= 0:
            k = A[i]
            b = bl(k)
            L[b].append(k)
            I[i] = b
            ANS[i] = bl(inf)
        for a in X[i][::-1]:
            if a != P[i]:
                P[a] = i
                for k in range(len(X[a])):
                    if X[a][k] == i:
                        del X[a][k]
                        break
                Q.append(~a)
                Q.append(a)
    return ANS

print("\n".join(map(str, EulerTour(N, X, 0))))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
a = list(map(int,input().split()))
ans = [0]*(n)
ki = [[]for i in range(n)]
dp = [0]*n
def dfs(now,last,path):
    nowp = a[now]
    
    for next in ki[now]:
        if next == last:continue
        dp[next] = 1
        for p in path:
            print(p)
            if a[p] < a[next]:dp[next] = max(dp[next],dp[p]+1)
        dfs(next,now,path+[next])
for i in range(n-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    ki[u].append(v)
    ki[v].append(u)
dp[0]  = 1
dfs(0,-1,[0])
print(*dp)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
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 = [0 for _ in range(n)]
memo = [0 for _ in range(n)]
seen = [False for _ in range(n)]
que = deque()
que.append(0)
memo[0] = a[0]
d[0] = 1
seen[0] = True

while len(que):
    cur = que.popleft()
    for to in edges[cur]:
        if not seen[to]:
            seen[to] = True
            if memo[cur] < a[to]:
                d[to] = d[cur] + 1
                memo[to] = a[to]
            else:
                d[to] = d[cur]
            que.append(to)

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

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

import sys
sys.setrecursionlimit(10**8)

class RangeMinimumQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.data = [0]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = 0
        while l < r:
            if r&1:
                r -= 1
                res = max(res, self.data[r-1])
            if l&1:
                res = max(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


n = int(input())
a = list(map(int, input().split()))
d = {j:i for i,j in enumerate(sorted(set(a)))}
m = len(d)
a = [d[i] for i in a]

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

RMQ = RangeMinimumQuery(m+10)
ans = [0]*n
def dfs(cur, prev):
    ai = a[cur]
    now = RMQ.query(ai, ai+1)
    nxt = max(RMQ.query(0, ai)+1, now)
    ans[cur] = nxt
    RMQ.update(ai, nxt)
    for to in G[cur]:
        if to != prev:
            dfs(to, cur)
    RMQ.update(ai, now)
dfs(0,-1)

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

Submission status: Wrong Answer

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**10]*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:
            if dp[idx[~q]] == a[~q]:
                dp[idx[~q]] = val[~q]
                eulerNum += 1

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

Submission status: Wrong Answer

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**10]*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: Wrong Answer

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]
            ans[v] = bisect.bisect_left(dp, INF) - 1
            dfs(v, u, dp)
            dp[i] = b
    dp = [INF] * (N+1)
    dp[0] = A[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: Wrong Answer

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    X[x].append(y)
    X[y].append(x)

def EulerTour(n, X, i0):
    def bl(k):
        l, r = -1, n-1
        while r - l > 1:
            m = (l + r) // 2
            if L[m][-1] < k:
                l = m
            else:
                r = m
        return l + 1

    inf = 1 << 20
    P = [-1] * n
    Q = [~i0, i0]
    ANS = [0] * n
    L = [[inf] for _ in range(n)]
    I = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~i
            L[I[i]].pop()
            continue
        if i >= 0:
            k = A[i]
            b = bl(k)
            L[b].append(k)
            I[i] = b
            ANS[i] = bl(inf)
        for a in X[i][::-1]:
            if a != P[i]:
                P[a] = i
                for k in range(len(X[a])):
                    if X[a][k] == i:
                        del X[a][k]
                        break
                Q.append(~a)
                Q.append(a)
    return ANS

print("\n".join(map(str, EulerTour(N, X, 0))))

Submission status: Wrong Answer

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] = bisect.bisect_left(dp, INF) -1
            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: Wrong Answer

Solution code:
import sys
import bisect
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
input = sys.stdin.readline


def inp():
    return int(input())


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


N = inp()

aa = inpl()
lines = [[] for _ in range(N)]
for _ in range(N - 1):
    s, t = inpl()
    s -= 1
    t -= 1
    lines[s].append(t)
    lines[t].append(s)

lines[0].append(-1)


ansl = [0] * N


def dfs(s, b, lis):
    global ansl

    a = aa[s]
    idx = bisect.bisect_right(lis, a)

    if len(lis) == idx:
        lis.append(a)
    else:
        lis[idx] = a

    ansl[s] = len(lis)

    flag = len(lines[s]) >= 3
    for t in lines[s]:
        if t == b:
            continue
        else:
            if flag:
                dfs(t, s, lis.copy())
            else:
                dfs(t, s, lis)


dfs(0, -1, [])


print("\n".join(map(str, ansl)))

Submission status: Wrong Answer

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

n = int(input())
A = [0] + list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(n-1)]


sys.setrecursionlimit(10**5 + 5)  # 再帰回数の上限！！


M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])


# 0-indexedの場合
V = [0] * (n+1)
# D = [-1] * (n+1)  # 自分を含む、子孫のノード数
ANS = [0] * (n+1)

R = [10**10] * (n+5)

import bisect

R[0] = 1
ANS[1] = 1

def des(x):
    # end = 1
    V[x] = 1
    # print(R[:10])


    for i in M[x]:
        if V[i] == 0:
            # print(i)
            # end = 0
            V[i] = 1
            ind = bisect.bisect_left(R, A[i])
            ma = R[ind]
            R[ind] = A[i]
            ANS[i] = bisect.bisect_left(R, 10**10-1)
            des(i)
            R[ind] = ma

    # if end == 1:
    #     print(R)
    #     ANS[x] = bisect.bisect_right(R, 10**10-1)

des(1)

for i in range(1, len(ANS)):
    print(ANS[i])

Submission status: Wrong Answer

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: Wrong Answer

Solution code:
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):
    ans = [1] * N
    cur = [[] for _ in xrange(N)]
    info = [None] * N
    VISIT, DO = 0, 1
    stack = [[0, -1, 1], [0,-1, 0]]
    cur[0].append(A[0])
    while stack:
        node, par, cmd = stack.pop()
        x = A[node]
        if cmd == VISIT:
            if par >= 0:
                lo = 0
                hi = ans[par]
                while lo < hi:
                    mi = lo + hi >> 1
                    if not cur[mi]:
                        hi = mi
                    elif cur[mi][-1] < x:
                        lo = mi + 1
                    else:
                        hi = mi
                i = lo
                cur[i].append(x)
                info[node] = i
                if i+1 > ans[node]:
                    ans[node] = i + 1

            
            for nei in graph[node]:
                if nei != par:
                    stack.append([nei, node, DO])
                    stack.append([nei, node, VISIT])
        else:
            if par >= 0:
                i = info[node]
                cur[i].pop()
    return ans

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: Wrong Answer

Solution code:
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):
    ans = [1] * N
    cur = [[] for _ in xrange(N)]
    info = [None] * N
    VISIT, DO = 0, 1
    stack = [[0,-1, 0]]
    cur[0].append(A[0])
    while stack:
        node, par, cmd = stack.pop()
        x = A[node]
        if cmd == VISIT:
            if par >= 0:
                lo = 0
                hi = ans[par]
                while lo < hi:
                    mi = lo + hi >> 1
                    if not cur[mi]:
                        hi = mi
                    elif cur[mi][-1] < x:
                        lo = mi + 1
                    else:
                        hi = mi
                i = lo
                cur[i].append(x)
                info[node] = i
                if i+1 > ans[node]:
                    ans[node] = i + 1

            stack.append([node, par, DO])
            for nei in graph[node]:
                if nei != par:
                    stack.append([nei, node, VISIT])
        else:
            if par >= 0:
                i = info[node]
                cur[i].pop()
    return ans

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