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:
import sys
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


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

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

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

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

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

        return


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

    S.recur(0)

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            paths.append(node)
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            while True:
                tmp = paths.pop()
                if tmp == parent:
                    paths.append(tmp)
                    paths.append(node)
                    break
                else:
                    idx, pre, pro, change = actions.pop()
                    dp[idx] = pre
                    ddp2[0] -= change


            idx = bin_search(dp[:len(paths)+1], a)
            if idx == float('inf'):
                actions.append((len(paths), float('inf'), a, 1))
                dp[len(paths)] = a
                ddp2[0] += 1
            else:
                if dp[idx] == float('inf'):
                    actions.append((idx, dp[idx], a, 1))
                    ddp2[0] += 1
                else:
                    actions.append((idx, dp[idx], a, 0))
                dp[idx] = a
        print(ddp2[0])
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)
    dfs(1)


    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    dp2 = [0] * (N+1)
    paths = []
    actions = []# (idx, pre, pro)
    def dfs(node, parent=None):
        a = A[node]
        seen[node] = True
        if parent == None:
            paths.append(node)
            actions.append((1, dp[1], a))
            dp[1] = a
        else:
            while True:
                tmp = paths.pop()
                if tmp == parent:
                    paths.append(tmp)
                    paths.append(node)
                    break
                else:
                    idx, pre, pro = actions.pop()
                    dp[idx] = pre


            idx = bin_search(dp[:len(paths)+1], a)
            if idx == float('inf'):
                actions.append((len(paths), float('inf'), a))
                dp[len(paths)] = a
            else:
                actions.append((idx, dp[idx], a))
                dp[idx] = a
        print(dp.index(float('inf'))-1)
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)
    dfs(1)


    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()

Submission status: Wrong Answer

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


from collections import defaultdict


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

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


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

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

    ans = [0]*N

    dp = [INF]*N
    event = []

    def dfs(curr, par):
        # print(par, curr, dp, event)
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            if dp[i] == INF:
                dp[i] = a[curr]
                event.append((curr, "A", i, a[curr]))
            else:
                dp[i] = a[curr]
                event.append((curr, "B", i, a[curr]))

        ans[curr] = i+1

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

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

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

    return


def main():

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
from bisect import bisect_right,bisect_left
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
edge=[[] for _ in range(n)]
for _ in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    edge[u].append(v)
    edge[v].append(u)
stack=deque([])
inf=10**18
lis=[inf]*(n+1)
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    idx=bisect_right(lis,a[s])
    stack.append((idx,lis[idx]))
    lis[idx]=a[s]
    ans[s]=bisect_left(lis,inf)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    lis[idx]=val
dfs(0)
#print(lis)
for i in range(n):
    print(ans[i])

Submission status: Wrong Answer

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


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


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

    def recur(self, i, pi=-1):
        rev_i = bisect(self.DP, self.A[i])
        if rev_i >= len(self.DP):
            self.DP.append(self.A[i])
            rev_v = None
        else:
            rev_v = self.A[rev_i]
            self.DP[rev_i] = self.A[i]
        self.ans[i] = len(self.DP)

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

        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


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

    S.recur(0)

    for i in range(N):
        print(S.ans[i])
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#入力高速化 + 再帰回数制限解除
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10000000)

from bisect import bisect_left,bisect_right
n=int(input())
a=list(map(int,input().split()))
edge=[[]for _ in range(n)]
for _ in range(n-1):
  u,v=map(int,input().split())
  u-=1
  v-=1
  edge[u].append(v)
  edge[v].append(u)
ans=[-1]*n
dp=[10**10]*n

#オイラーツアー
#n=頂点数、s=始点、edge=隣接リスト
#木構造を投げると訪問順listが帰ってくる、|ans|=2*n-1
#適宜書き換えて実装を楽にしましょう
def EulerTour(n,s,e):
  EulerTour_list=[]
  def EulerTour_dfs(i,root):
    EulerTour_list.append(i)
    ind=bisect_right(dp,a[i])
    bef=dp[ind]
    dp[ind]=a[i]
    ans[i]=bisect_left(dp,10**10)
    for j in e[i]:
      if j!=root:
        EulerTour_dfs(j,i)
    if root!=-1:
      EulerTour_list.append(root)
      dp[ind]=bef
  EulerTour_dfs(s,-1)
  return EulerTour_list

EulerTour(n,0,edge)
print(*ans)

Submission status: Wrong Answer

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

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_right(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        if L[i] > a:
            L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')

Submission status: Wrong Answer

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

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

edges = [[] for _ in range(N)]
for _ in range(N - 1):
    fr, to = map(lambda a: int(a) - 1, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

ans = [0] * N
L = [-10**18]

def search(now, pr):
    a = A[now]
    i = bisect_right(L, a)
    isAppended = False
    prevValue = -1

    if i == len(L):
        L.append(a)
        isAppended = True
    else:
        prevValue = L[i]
        L[i] = a

    ans[now] = len(L) - 1

    for to in edges[now]:
        if to == pr:
            continue
        search(to, now)

    if isAppended:
        L.pop()
    else:
        L[i] = prevValue

search(0, -1)
print(*ans, sep='\n')

Submission status: Wrong Answer

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


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


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

    def recur(self, i, pi=0):
        rev_i = bisect(self.DP, self.A[i - 1])
        if rev_i == len(self.DP):
            self.DP.append(self.A[i - 1])
            rev_v = None
        else:
            rev_v = self.A[rev_i]
            self.DP[rev_i] = self.A[i - 1]
        self.ans[i] = len(self.DP)

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

        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


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

    S.recur(1)

    for i in range(1, N + 1):
        print(S.ans[i])
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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


class solve:
    def __init__(self, N):
        self.ans = {}
        self.DP = []
        self.visited = [False] * (N + 1)

    def recur(self, i):
        if self.visited[i] is True:
            return
        else:
            self.visited[i] = True
        rev_i = bisect(self.DP, self.A[i - 1])
        if rev_i == len(self.DP):
            self.DP.append(self.A[i - 1])
            self.ans[i] = len(self.DP)
            rev_v = None
        else:
            rev_v = self.A[rev_i]
            self.DP[rev_i] = self.A[i - 1]
            self.ans[i] = len(self.DP)

        for nv in self.edges[i]:
            self.recur(nv)

        if rev_v is None:
            self.DP.pop()
        else:
            self.DP[rev_i] = rev_v

        return


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

    for i in range(1, N + 1):
        print(S.ans[i])
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
a = list(map(int, input().split()))
graph = [[] for _ in range(N)]
for _ in range(N-1):
    u,v = map(lambda x: int(x) -1 , input().split())
    graph[u].append(v)
    graph[v].append(u)
ans = [0 for _ in range(N)]
import sys
from typing import List
sys.setrecursionlimit(10**7)
def recursion(ind, dp:List[int] , visited):
    if visited[ind] > 0 : return
    if len(dp) == 0 or dp[-1] < a[ind]:
        dp.append(a[ind])
        visited[ind] = len(dp)-1
        for v in graph[ind]:
            recursion(v,dp,visited)
        dp.pop()
        return
    else :
        left, right = 0, len(dp)
        while right - left > 1:
            mid = (right + left) //2
            if dp[mid] < a[ind]:
                left = mid
            else :
                right = mid

        tmp = dp[left+1]
        dp[left+1] = min(tmp, a[ind])
        visited[ind] = left + 1
        for v in graph[ind]:
            recursion(v, dp, visited)
        dp[left+1] = tmp
recursion(0, [0], ans)
for t in ans:
    print(t)

Submission status: Wrong Answer

Solution code:
import collections
import bisect
import sys

sys.setrecursionlimit(10 ** 6)

def f(v):
    #state[v] = 1
    a=As[v]
    idx = bisect.bisect_left(D,a)
    stack.append( (idx,D[idx]) ) # push
    D[idx] = a
    
    ans[v] = bisect.bisect_left(D,float('inf'))

    for u in V[v]:
        # if state[u] == 1: 木構造なので不要
        f(u)

    # 巻き戻し
    i_pre,d_pre=stack.pop()
    D[i_pre] = d_pre



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

D=[float('inf')]*N
stack=collections.deque([])
ans=[0]*N
#state=[0]*N

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

f(0)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import resource

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, dp, nbs, cidx):
    ca = a[cur]

    oidx = 0
    ov = 0
    
    nidx = cidx
    for i in range(cidx, n):
        if dp[i] >= ca:
            ov = dp[i]
            oidx = i
            dp[i] = ca
            mlen[cur] = i + 1
            ndix = i
            break

    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, dp, nbs, nidx)

    dp[oidx] = ov
    return


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

nbs = [ [] for i in range(n) ]

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


mlen = [ 0 for i in range(n) ]
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, dp, nbs, 0)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import resource

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, st, dp, nbs):
    ca = a[cur]
    
    for i in range(n):
        if dp[i] >= ca:
            st.append((i, dp[i], ca))
            dp[i] = ca
            mlen[cur] = i + 1
            break

    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, st, dp, nbs)

    (idx, ov, nv) = st.pop(-1)
    dp[idx] = ov
    return


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

nbs = [ [] for i in range(n) ]

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


mlen = [ 0 for i in range(n) ]
st = []
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, st, dp, nbs)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import resource

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, st, dp, nbs):
    ca = a[cur]
    
    for i in range(n):
        if dp[i] >= ca:
            st.append((i, dp[i], ca))
            dp[i] = ca
            mlen[cur] = i + 1
            break

    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, st, dp, nbs)

    (idx, ov, nv) = st.pop()
    dp[idx] = ov
    return


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

nbs = [ [] for i in range(n) ]

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


mlen = [ 0 for i in range(n) ]
st = []
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, st, dp, nbs)

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

import sys
import resource

sys.setrecursionlimit(1000000)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

def getmlen(cur, p, n, a, mlen, st, dp, nbs):
    ca = a[cur]
    
    for i in range(n):
        if dp[i] > ca:
            st.append((i, dp[i], ca))
            dp[i] = ca
            mlen[cur] = i + 1
            break

    for ch in nbs[cur]:
        if ch == p:
            continue

        getmlen(ch, cur, n, a, mlen, st, dp, nbs)

    (idx, ov, nv) = st.pop()
    dp[idx] = ov
    return


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

nbs = [ [] for i in range(n) ]

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


mlen = [ 0 for i in range(n) ]
st = []
dp = [ float('inf') for i in range(n) ]

getmlen(0, -1, n, a, mlen, st, dp, nbs)

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Edge=[[] for _ in range(N)]
loute=[str(0)]*N
for i in range(N-1):
    u,v=map(int,input().split())
    Edge[u-1].append(v-1)

tmp=deque(str(0))
cost=[-1]*N
while tmp:
    T0=int(tmp.pop())
    
    for i in Edge[T0]:
        tmp.append(i)
        loute[i]=loute[T0]+str(i)
    
    if cost[T0]==-1:
        cost[T0]=1
    for i in loute[T0]:
        if A[int(i)]<A[T0]:
            cost[T0]=max(cost[int(i)]+1,cost[T0])
            
for i in range(N):
    print(cost[i])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)

N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * N
tree = defaultdict(list)
for _ in range(N - 1):
	u, v = list(map(int, input().split()))
	tree[u-1].append(v-1)
	tree[v-1].append(u-1)

dp[0] = A[0]
ans = [1] * N
def backtrack(node, visited, tail_idx):
	flag = any([nx not in visited for nx in tree[node]])
	if not flag:
		return
	for nx in tree[node]:
		if nx in visited:
			continue
		visited.add(nx)
		idx = bisect_left(dp, A[nx])
		prev = dp[idx]
		if tail_idx < idx:
			dp[idx] = A[nx]
			new_tail_idx = idx
			ans[nx] = new_tail_idx + 1
			backtrack(nx, visited, new_tail_idx)
		elif A[nx] < dp[idx]:
			dp[idx] = A[nx]
			ans[nx] = tail_idx + 1
			backtrack(nx, visited, tail_idx)
		else:
			ans[nx] = tail_idx
			backtrack(nx, visited, tail_idx)
		dp[idx] = prev
		visited.remove(nx)

backtrack(node=0, visited={0}, tail_idx=0)
for i in ans:
	print(i)

Submission status: Wrong Answer

Solution code:
import collections
import bisect
import sys

sys.setrecursionlimit(10 ** 6)

def f(v):
    #state[v] = 1
    a=As[v]
    idx = bisect.bisect_left(D,a)
    stack.append( (idx,D[idx]) ) # push
    D[idx] = a
    
    ans[v] = bisect.bisect_left(D,float('inf'))

    for u in V[v]:
        # if state[u] == 1: 木構造なので不要
        len_pre=len(stack)
        
        f(u)

        # 巻き戻し
        while len(stack) > len_pre:
            i_pre,d_pre=stack.pop()
            D[i_pre] = d_pre



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

D=[float('inf')]*N
stack=collections.deque([])
ans=[0]*N
#state=[0]*N

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

f(0)

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

Submission status: Wrong Answer

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

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

lis = [a[0]]
ret = [0] * N
def dfs(cur, pre) :
  for nex in vec[cur] :
    if nex == pre : continue
    if a[nex] > lis[-1] :
      lis.append(a[nex])
      ret[nex] = len(lis)
      dfs(nex, cur)
      lis.pop()
    else :
      pos = bisect_left(lis, a[nex])
      v = lis[pos]
      lis[pos] = a[nex]
      ret[nex] = pos + 1
      dfs(nex, cur)
      lis[pos] = v

dfs(0, -1)

ret[0] = 1
for i in range(N) :
  print(ret[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
from collections import deque

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

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
INF=float('inf')
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = i

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

Edge=[[] for _ in range(N)]
loute=[str(0)]*N
for i in range(N-1):
    u,v=map(int,input().split())
    Edge[u-1].append(v-1)

tmp=deque(str(0))
cost=[0]*N
while tmp:
    T0=int(tmp.pop())
    
    for i in Edge[T0]:
        tmp.append(i)
        loute[i]=loute[T0]+str(i)
    
    for i in loute[T0]:
        if A[int(i)]<A[T0]:
            cost[T0]=max(cost[int(i)]+1,cost[T0])
            
for i in range(N):
    print(cost[i]+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
import bisect
import copy
from collections import deque
sys.setrecursionlimit(10**7)

def main():
    N = int(input())
    a = list(map(int,input().split()))
    INF = 10**12
    
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u,v = map(int,input().split())
        edge[u-1].append(v-1)
        edge[v-1].append(u-1)
        
    def LIS(dp,num):
        ind = bisect.bisect_left(dp,num)
        ret = dp[ind]
        dp[ind] = num
        return ind,ret
    
    dp = [INF]*(N+2)
    dp[0] = -INF
    dp[1] = a[0]

    ans = [0]*N
    q = deque([])
    
    def DFS(prev,now,dp):
        while q:
            s,t,ind,num = q.pop()
            if t == prev:
                q.append((s,t,ind,num))
                break
            else:
                dp[ind] = num
        ind,num = LIS(dp,a[now])
        ans[now] = ind
        q.append((prev,now,ind,num))
        for fol in edge[now]:
            if fol != prev:
                DFS(now,fol,dp)

    DFS(-1,0,dp)
    print(*ans,sep="\n")
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    a = list(map(int,input().split()))
    INF = 10**12
    
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u,v = map(int,input().split())
        edge[u-1].append(v-1)
        edge[v-1].append(u-1)
        
    def LIS(dp,num):
        ind = bisect.bisect_left(dp,num)
        ret = dp[ind]
        dp[ind] = num
        return ind,ret
    
    dp = [INF]*(N+2)
    dp[0] = -INF

    ans = [0]*N
    
    def DFS(prev,now,dp):
        ind,_ = LIS(dp,a[now])
        ans[now] = ind
        for fol in edge[now]:
            original_dp = copy.deepcopy(dp)
            if fol != prev:
                DFS(now,fol,original_dp)

    DFS(-1,0,dp)
    print(*ans,sep="\n")
 
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    e = dp[b]
    x = len(e)
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        if e[-1] < c:
            dp[i] = e.copy()+[c]
            ans[i] = x+1
            d = dp[i][::-1][1:]
        else:
            dp[i] = e.copy()
            ans[i] = x
            d = dp[i][::-1]
        for j,k in enumerate(d):
            if j == x-1 and k > c:
                k = c
            elif j == 0:
                y = k
            elif k > c and y < c:
                k = c
            y = k
                
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    *A,=map(int, input().split())
    G=[[] for _ in range(N)]
    for _ in range(N-1):
        u,v=map(int, input().split())
        u,v=u-1,v-1
        G[u].append(v)
        G[v].append(u)

    INF=10**10
    ans=[0]*N
    l=[INF]*(N+1)
    stk=[(0,0,0)]
    while stk:
        s,a,b=stk.pop()
        if s==0:
            i=bisect_right(l,A[a])
            stk.append((1,i,l[i]))
            l[i]=A[a]
            ans[a]=bisect_left(l,INF)
            for to in G[a]:
                if ans[to]>0: continue
                stk.append((0,to,0))
        else:
            l[a]=b
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!python3

import sys
sys.setrecursionlimit(10 ** 6)

import numpy as np


INF = 10 ** 10

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


def dfs(l, visit, link, v, dp):
    visit[v] = True
    # LIS
    if dp[-1] < A[v]:
        dp = np.append(dp, A[v])
    else:
        i = np.searchsorted(dp, A[v])
        dp[i] = A[v]
    l[v] = len(dp)

    for x in link[v]:
        if not visit[x]:
            dfs(l, visit, link, x, dp)


def main():
    link = [[] for _ in range(N)]
    for u, v in uv:
        link[u - 1].append(v - 1)
        link[v - 1].append(u - 1)
    
    visit = [False] * N
    l = [None] * N
    dfs(l, visit, link, 0, np.array([A[0]]))
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()