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:

N=int(input())
a=[int(x) for x in input().split()]
v=[]
for i in range(N-1):
    v.append([int(x) for x in input().split()])


m={}
m[0]=1
seen=[0]
unseen_v=v
seen_v=[]

def newlen(m,b_index,a_index):
    if a[b_index]<a[a_index]:
        return m[b_index]+1
    else:
        return m[b_index]

while unseen_v != []:
    for i in unseen_v:
        if i[0]-1 in m:
            new=i[1]-1
            seen.append(new)
            m[new]=newlen(m,i[0]-1,new)
            seen_v.append(i)
            unseen_v.remove(i)

            print('m=',m,'seen_v=',seen_v)
    
    for i in unseen_v:
        if i[1]-1 in m:
            new=i[0]-1
            seen.append(new)
            m[new]=newlen(m,i[1]-1,new)
            seen_v.append(i)
            unseen_v.remove(i)
            print('m=',m,'seen_v=',seen_v)
for i in range(N):
    print(m[i])

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

def binary_search(l, value, over):
    """
    flg_same: bool

    l = [0, 10, 20]
    first_over(l, 9) # 1, 10
    first_over(l, 10) # 2, 20
    first_over(l, 10, True) # 1, 10
    first_over(l, -10) # 0, 0
    first_over(l, 100) # None, None
    """
    # assert: l is sorted
    if len(l) == 0:
        return None, None
    b = 0 # bottom
    t = len(l) - 1 # top
    if not over(l[t], value):
        return None, None
    while not (b == t):
        head = b + ((t - b) // 2)
        if over(l[head], value):
            t = head
        else:
            b = head + 1
    return b, l[b]

def first_over_or_same(l, value):
    def over_or_same(a, b):
        return a >= b
    return binary_search(l, value, over_or_same)

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        return -1
        self.dp.append(math.inf)
        self.history.append(None)
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        return -1
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        d = self.history[-1]
        self.dp[d.dp_key] = d.before_value

    def use(self, value):
        key, over_value = first_over_or_same(self.dp, value)
        if key is not None and over_value != value:
            self.history[-1] = SolverLIS.Diff(key, self.dp[key])
            self.dp[key] = value


    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

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








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Wrong Answer

Solution code:
import bisect

INF = 10 ** 10

N = int(input())
As = 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)

parents = []

dfs_stack = [0]
ans = [-1] * N
lis = [INF] * (N+1)
rewinder = []

while dfs_stack:
    pos = dfs_stack.pop()
    for next_node in edges[pos]:
        if ans[next_node] == -1:
            dfs_stack.append(next_node)
        else:
            parent = next_node
    
    while rewinder:
        i, before, after = rewinder.pop()
        if after == As[parent]:
            rewinder.append( (i, before, after) )
            break
        else:
            lis[i] = before

    index = bisect.bisect_left(lis, As[pos])
    rewinder.append( (index, lis[index], As[pos]) )
    lis[index] = As[pos]
    ans[pos] = lis.index(INF)

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

Submission status: Wrong Answer

Solution code:
import bisect

INF = 10 ** 10

N = int(input())
As = 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)

parents = []

dfs_stack = [0]
ans = [-1] * N
lis = [INF] * (N+1)
rewinder = []

while dfs_stack:
    pos = dfs_stack.pop()
    for next_node in edges[pos]:
        if ans[next_node] == -1:
            dfs_stack.append(next_node)
        else:
            parent = next_node
    
    while rewinder:
        i, before, after = rewinder.pop()
        if after == As[parent]:
            rewinder.append( (i, before, after) )
            break
        else:
            lis[i] = before

    index = bisect.bisect_left(lis, As[pos])
    rewinder.append( (index, lis[index], As[pos]) )
    lis[index] = As[pos]
    ans[pos] = lis.index(INF)

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n, arr):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(arr, INF)
    answer[n] = i
    print('n, i', n, i, arr[:5])
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        new = arr[:]
        i = bisect_left(new, A[c])
        new[i] = A[c]
        dfs(c, new)

B = [INF] * (N+1)
B[0] = A[1]
dfs(1, B)
for a in answer[1:]:
    print(a)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
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


#ダイクストラ(参照:https://gside.org/blog/2019/12/01/, https://ta7uw.hatenablog.com/entry/2018/09/30/222102)
class Node(object):#頂点
    def __init__(self,  value: int):
        self.value = value

    def getValue(self) -> int:
        return self.value

    def __str__(self):
        return str(self.value)

    def __lt__(seif, other):
        return None


class WeightedEdge(object):#重み付き枝
    def __init__(self, src: Node, dest: Node, weight: int):
        self.src = src
        self.dest = dest
        self.weight = weight

    def getSource(self) -> Node:
        return self.src

    def getDestination(self) -> Node:
        return self.dest

    def getWeight(self) -> int: 
        return self.weight

    def __str__(self):
        return str(self.src.getValue()) + '->('  + str(self.getWeight()) + ')->' + str(self.dest.getValue())


class Digraph(object):#有向グラフ
    def __init__(self):
        self.nodes = []
        self.edges = {}
        self.size = 0

    def addNode(self, node: Node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
            self.size += 1
    
    def addEdge(self, edge: WeightedEdge):
        src = edge.getSource()
        dest = edge.getDestination()
        weight = edge.getWeight()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not a graph')

        self.edges[src].append((weight, dest))
    
    def childrenOf(self, node: Node) -> list:#element : tuple
        return self.edges[node]
    
    def __str__(self):
        result = ''
        for src in self.nodes:
            for weightdest in self.edges[src]:
                dest  = weightdest[1]
                result += str(src.getValue()) + '->' + str(dest.getValue()) + '\n'
        return result[:-1]


class RingBuffer(object):
    def __init__(self, size: int):
        self.ringsize = size
        self.size = 0
        self.ring = [None]*size
        self.head = 0
        self.tail = 0
    def enring(self, a: int):
        if self.tail != self.head or self.ring[self.tail] == None:
            self.ring[self.tail] = a
            self.tail += 1
            self.tail %= self.ringsize
            self.size += 1
        else:
            print('Error : This Ring Buffer is full.')
    def dering(self):
        if self.head != self.tail:
            tmp = self.ring[self.head]
            self.ring[self.head] = None # なくてもよい．
            self.head += 1
            self.head %= self.ringsize
            self.size -= 1
            return tmp
        else:
            print(self.head, self.tail)
            print('Error : This Ring Buffer is empty.')


def getPath(goalNode, prev):
    path = [goalNode]
    dest = goalNode.getValue()
    while prev[dest] != float('inf'):
        path.append(prev[dest])
        dest = prev[dest].getValue()
    return list(reversed(path))


def Dijkstra(graph: Digraph, startNode: Node, goalNode: Node = None) -> list:#Reture a list that has minimum distances from the start point to each point
    dist = [float('inf') for _ in range(graph.size)]
    prev = [float('inf') for _ in range(graph.size)]

    dist[startNode.getValue()] = 0
    srcque = RingBuffer(graph.size)
    costque = RingBuffer(graph.size)
    
    srcque.enring(startNode)
    costque.enring(0)
    while srcque.size != 0:
        srcNode = srcque.dering()
        prev_cost = costque.dering()

        if dist[srcNode.getValue()] < prev_cost:
            continue
        
        for cost, destNode  in graph.childrenOf(srcNode):
            if cost != float('inf') and dist[destNode.getValue()] > dist[srcNode.getValue()] + cost:
                dist[destNode.getValue()] = dist[srcNode.getValue()] + cost
                srcque.enring(destNode)
                costque.enring(dist[destNode.getValue()])
                prev[destNode.getValue()] = srcNode
    if goalNode == None:
        return dist, prev
    else:
        return getPath(goalNode, prev)


def BinarySearch(num, nums):
    if len(nums) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(nums)
    while left < right:
        mid  = (left+right)//2
        if num < nums[mid]:
            right = mid
        else:
            left = mid + 1
    return right


def LIS(seq):
    LISs = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > LISs[-1]:
            LISs.append(seq[i])
        else:
            LISs[BinarySearch(seq[i], LISs)-1] = seq[i]
    return len(LISs)


def main():
    n = ni()
    As = na()
    d = Digraph()
    Nodes = [Node(i) for i in range(n)]
    for node in Nodes:
        d.addNode(node)
    for _ in range(n-1):
        u,v = na()
        d.addEdge(WeightedEdge(Nodes[u-1],Nodes[v-1],1))
        d.addEdge(WeightedEdge(Nodes[v-1],Nodes[u-1],1))
    dist, prev = Dijkstra(d, Nodes[0])
    for k in range(n):
        ss = [As[node.getValue()] for node in getPath(Nodes[k], prev)]
        print(LIS(ss))
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(300000)


def dfs(cur, prev, lis, A, adj, ans):
    idx = bisect_left(lis, A[cur])
    if idx == len(lis):
        save = None
        lis.append(A[cur])
    else:
        save = A[idx]
        lis[idx] = A[cur]
    ans[cur] = len(lis)
    for nxt in adj[cur]:
        if nxt == prev:
            continue
        dfs(nxt, cur, lis, A, adj, ans)
    if save is None:
        lis.pop()
    else:
        lis[idx] = save


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    dfs(0, -1, [], A, adj, ans)
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [INF] * (n + 1)
    dp[0] = -INF
    res = 0
    ans = [None] * n
    change = [None] * n
    stack = [(0, -1)]

    while stack:
        v, p = stack.pop()
        if v >= 0:
            idx = bisect_left(dp, A[v])
            change[v] = (idx, dp[idx])
            res = max(res, idx)
            ans[v] = res
            dp[idx] = A[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            idx, prev = change[v]
            dp[idx] = prev
            res = dp[p]

    print(*ans)
resolve()

Submission status: Wrong Answer

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

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

ans = [0 for i in range(n)]
dp = [10**10 for _ in range(n+1)]
check = [True for _ in range(n)]
def dfs(now):
    check[now] = False
    ite = bisect_left(dp, a[now])
    ans[now] = ite+1
    tmp = dp[ite]
    dp[ite] = a[now]
    for to in G[now]:
        if check[to]:
            dfs(to)
    dp[ite] = tmp

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

Submission status: Wrong Answer

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

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

ans = [0 for i in range(n)]
dp = [10**10 for _ in range(n+1)]
check = [True for _ in range(n)]
def dfs(now):
    check[now] = False
    ite = bisect_left(dp, a[now])
    ans[now] = ite+1
    tmp = dp[ite]
    dp[ite] = a[now]
    for to in G[now]:
        if check[to]:
            dfs(to)
    dp[ite] = tmp

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

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        p,q = map(int,input().split())
        p -= 1
        q -= 1
        g[p].append(q)
        g[q].append(p)
    dis = [10**10]*n
    dis[0] = 0
    que = deque()
    que.append(0)
    pr = [0 for _ in range(n)]
    pr[0] = 1
    ans = ['' for _ in range(n)]
    ans[0] = [a[0]]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] <= dis[go] + 1:
                continue
            lis = ans[go]
            if a[g[go][i]] > ans[go][-1]:
                ans[go].append(a[g[go][i]])
            else:
                ans[go][bisect.bisect_left(ans[go],a[g[go][i]])] = a[g[go][i]]
            ans[g[go][i]] = ans[go]
            dis[g[go][i]] = dis[go] + 1
            ans[go] = copy.copy(lis)
            que.append(g[go][i])
    for i in range(n):
        print(len(ans[i]))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        p,q = map(int,input().split())
        p -= 1
        q -= 1
        g[p].append(q)
        g[q].append(p)
    dis = [10**10]*n
    dis[0] = 0
    que = deque()
    que.append(0)
    pr = [0 for _ in range(n)]
    pr[0] = 1
    ans = ['' for _ in range(n)]
    ans[0] = [a[0]]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] <= dis[go] + 1:
                continue
            lis = ans[go]
            if a[g[go][i]] > ans[go][-1]:
                ans[go].append(a[g[go][i]])
            else:
                ans[go][bisect.bisect_left(ans[go],a[g[go][i]])] = a[g[go][i]]
            ans[g[go][i]] = ans[go]
            dis[g[go][i]] = dis[go] + 1
            ans[go] = lis
            que.append(g[go][i])
    for i in range(n):
        print(len(ans[i]))
    
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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



idle_max=10**18

stack=deque([0])
visited={0}

miti_to_0=[-1 for i in range(N)]
miti=[set() for i in range(N)]

while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            miti_to_0[p]=a
            miti[a].add(p)
            stack.append(p)

stack=[0]
visited={0}
dp=[A[0]]
decodelst=[]
dic=defaultdict(int)
dic[0]=1
while stack:
    #print(dp)
    a=stack.pop()
    if miti[a]:
        p=miti[a].pop()

        if A[p]>dp[-1]:

            decodelst.append([len(dp),A[p],-1])
            dp.append(A[p])
            dic[p]=len(dp)


        else:
            i=bisect_left(dp,A[p])
            decodelst.append([i,A[p],dp[i]])
            dp[i]=A[p]
            dic[p]=len(dp)
        stack.append(p)
    else:
        if miti_to_0[a]==-1:
            break
        i,p,f=decodelst.pop()
        if f==-1:
            dp.pop()
        else:
            dp[i]==f
        stack.append(miti_to_0[a])
for i in range(N):
    print(dic[i])

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()

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



idle_max=10**18

stack=deque([0])
visited={0}

miti_to_0=[-1 for i in range(N)]
miti=[set() for i in range(N)]

while stack:
    a=stack.popleft()
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            miti_to_0[p]=a
            miti[a].add(p)
            stack.append(p)

stack=[0]
visited={0}
dp=[0]
decodelst=[]
dic=defaultdict(int)
dic[0]=1
while stack:
    #print(dp)
    a=stack.pop()
    if miti[a]:
        p=miti[a].pop()

        if A[p]>dp[-1]:

            decodelst.append([len(dp),A[p],-1])
            dp.append(A[p])
            dic[p]=len(dp)


        else:
            i=bisect_left(dp,A[p])
            decodelst.append([i,A[p],dp[i]])
            dp[i]=A[p]
            dic[p]=len(dp)
        stack.append(p)
    else:
        if miti_to_0[a]==-1:
            break
        i,p,f=decodelst.pop()
        if f==-1:
            dp.pop()
        else:
            dp[i]==f
        stack.append(miti_to_0[a])
for i in range(N):
    print(dic[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect
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 = 10 ** 10
dp = [INF] * (N + 2)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, -1)])  # (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(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # 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 bisect import bisect
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 = 10 ** 9 + 7
dp = [INF] * (N + 2)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, -1)])  # (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(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # 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:
import sys
from bisect import bisect
sys.setrecursionlimit(10 ** 9)

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 = 10 ** 9 + 7
dp = [INF] * (N + 2)
dp[0] = -INF
ans = [0] * N

def dfs(u, p=-1):
    # Update dp
    i = bisect(dp, A[u])
    old = dp[i]
    dp[i] = A[u]

    # Calc ans
    ans[u] = i
    if p != -1:
        ans[u] = max(ans[u], ans[p])

    # Go to next
    for v in graph[u]:
        if v == p:
            continue
        dfs(v, u)

    # Restore
    dp[i] = old

dfs(0)
print(*ans)

Submission status: Wrong Answer

Solution code:
import bisect

MAX = 10 ** 9 + 1
N = int(input())
a_list = list(map(int, input().split()))

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

stack = [[0, 0, 1, MAX]]

results = [None] * N
results[0] = 1
longests = [MAX] * (N + 1)
longests[0] = 0
while stack:
	pair = stack[-1]
	cur, index, org_i, org_v = pair
	a = a_list[cur]
	
#	print(cur, st.data_table[0][1])
	
	neighbours = graph[cur]
	if index >= len(neighbours):
		longests[org_i] = org_v
		stack.pop()
	else:
		nxt = neighbours[index]
		if results[nxt] == None:
			n_a = a_list[nxt]
			l = bisect.bisect_left(longests, n_a)
			results[nxt] = l + 1
			n_org_v = longests[l]
			longests[l] = n_a
			stack.append([nxt, 0, l, n_org_v])
		pair[1] = index + 1

for l in results:
	print(l)

Submission status: Wrong Answer

Solution code:
class SegmentTree:
	def __init__(self, n, *, init = None, data = None, merge = None, update = None, list = list):
		if init != None and data != None:
			raise Error("init and data cannot be specified at a time")
		if init == None and data == None:
			init = lambda l, r: []
		self.n = n
		data_table = []
		if data:
			data_table.append((1, data))
		else:
			data_table.append((1, list(init(i, i + 1) for i in range(n))))
		
		w = 2
		if merge == None:
			while w <= n:
				data_table.append((w, list(init(i, i + w) for i in range(0, ((n - 1) // w + 1) * w, w))))
				w *= 2
		else:
			last_data = data_table[0][1]
			while w <= n:
				if len(last_data) % 2 == 0:
					new_data = list(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w + 1))
				else:
					new_data = list(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (n - 1) // w)) + list((merge(last_data[-1], None), ))
				data_table.append((w, new_data))
				last_data = new_data
				w *= 2
		self._update = update
		self.data_table = data_table
	
	def update(self, i, value):
		if self._update != None:
			data = self.data_table[0][1]
			data[i] = value
			last_data = data
			for w, data in self.data_table[1:]:
				j = i // w
				k = j * 2
				if k + 1 < len(last_data):
					data[j] = self._update(data[j], last_data[k], last_data[k + 1])
				else:
					data[j] = self._update(data[j], last_data[k], None)
					pass
				last_data = data
		else:
			raise Error("update method not given")
	
	def data_at(self, i):
		for w, data_list in self.data_table:
			yield data_list[i // w]
	
	def data_range(self, s, e = None):
		if e == None:
			e = s
			s = 0
		if s == 0:
			for w, data_list in reversed(self.data_table):
				if e % (w * 2) >= w:
					yield data_list[e // w - 1]
		elif s < e:
			for w, data_list in self.data_table:
				w2 = w * 2
				m = s % w2
				new_s = s + w2 - m
				if new_s > e:
					break
				if m != 0:
					yield data_list[s // w]
					s = new_s
			if s == e:
				return
			for w, data_list in reversed(self.data_table):
				new_s = s + w
				if new_s <= e:
					yield data_list[s // w]
					s = new_s
	
	def check(self, merge):
		last_data = self.data_table[0][1]
		for w, data in self.data_table[1:]:
			if len(last_data) % 2 == 0:
				new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (self.n - 1) // w + 1))
			else:
				new_data = tuple(merge(last_data[i * 2], last_data[i * 2 + 1]) for i in range(0, (self.n - 1) // w)) + (last_data[-1], )
			if new_data != data:
				print(new_data)
				print(data)
				raise "hoge"
			last_data = new_data
			w *= 2
	
	def output(self, func = None):
		if func == None:
			func = lambda x: str(x)
		for w, data_list in self.data_table:
			print(f"#{w}: " + ", ".join(func(data) for data in data_list))
			pass

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

a_items = list(set(a_list))
a_items.sort()
a_table = {}
for i, a in enumerate(a_items):
	a_table[a] = i

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

def merge(d1, d2):
	if d1 == None:
		return d2
	if d2 == None:
		return d1
	return max(d1, d2)

data = [None] * len(a_table)
st = SegmentTree(len(a_table), data = data, merge = merge, update = lambda d, d1, d2: merge(d1, d2))

stack = [[0, 0, None]]
st.update(a_table[a_list[0]], 1)

results = [None] * N
results[0] = 1
while stack:
	pair = stack[-1]
	cur, index, org = pair
	a = a_table[a_list[cur]]
	
#	print(cur, st.data_table[0][1])
	
	neighbours = graph[cur]
	if index >= len(neighbours):
		st.update(a, org)
		stack.pop()
	else:
		nxt = neighbours[index]
		if results[nxt] == None:
			n_a = a_table[a_list[nxt]]
			if n_a > 0:
				l = None
				for d in st.data_range(n_a):
					if l == None or (d != None and l < d):
						l = d
				if l == None:
					l = 0
			else:
				l = 0
			results[nxt] = l + 1
			n_org = st.data_table[0][1][n_a]
			st.update(n_a, l + 1)
			stack.append([nxt, 0, org])
		pair[1] = index + 1

for l in results:
	print(l)