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
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


from bisect import bisect_left, bisect_right, insort_left
from collections import deque


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html
        ls ... 渡す初期配列
        '''
        self.bst = deque(sorted(ls))  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __repr__(self):
        return f'BST:{self.bst}'

    def __len__(self):
        return len(self.bst)

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) + 1
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

# 各ノードに今までの最長増加部分列と現在の増加部分列長の記録があれば、たかだた分岐地点から探索できるのでは？
N = read_a_int()
A = read_ints()
Tree = defaultdict(lambda: [])
for _ in range(N - 1):
    u, v = read_ints()
    u -= 1
    v -= 1
    Tree[u].append(v)
    Tree[v].append(u)

LIS = BinarySearchTree([-1])

ans = [-1] * N


# def dfs(u, p, LIS):  # これって参照渡しに成るんすかねすると厄介かもしれない
#     '''現在のノード、親、最長増加部分列の状態'''
#     LIS.insert_replace_right(A[u])
#     ans[u] = len(LIS) - 1
#     if len(Tree[u]) == 2:  # 参照渡しでok
#         for nu in Tree[u]:
#             if nu == p:
#                 continue
#             dfs(nu, u, LIS)

#     if len(Tree[u]) > 2:  # 配列のコピーを渡す
#         LIS = BinarySearchTree(LIS.bst.copy())
#         for nu in Tree[u]:
#             if nu == p:
#                 continue
#             dfs(nu, u, LIS)


def dfs(u, p, LIS, lis):  # これって参照渡しに成るんすかねすると厄介かもしれない
    '''現在のノード、親、最長増加部分列の状態'''
    LIS.insert_replace_right(A[u])
    ans[u] = lis + len(LIS) - 1
    for nu in Tree[u]:
        if nu == p:
            continue
        # print(LIS.bst[-1])
        # print(ans[u])
        dfs(nu, u, BinarySearchTree([LIS.bst[-1]]), ans[u])


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

Submission status: Wrong Answer

Solution code:
from collections import deque
n=int(input())
A=list(map(int,input().split()))
graph=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1;b-=1
    graph[a].append(b)
    graph[b].append(a)
length=[1]*n
maxn=[-1]*n
maxn[0]=A[0]
D=deque([0])
while D:
    v=D.popleft()
    for i in graph[v]:
        if maxn[i]!=-1:continue
        if A[i]>maxn[v]:length[i]=length[v]+1;maxn[i]=A[i]
        else:length[i]=length[v];maxn[i]=maxn[v]
        D.append(i)
for i in range(n):
    print(length[i])

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect_left
n=int(input())
*a,=map(int,input().split())
st=[list(map(int,input().split())) for _ in range(n-1)]
con=[[] for _ in range(n)]
val=[i<<32+x for i,x in enumerate(a)]
for s,t in st:
	con[s-1].append(t-1)
	con[t-1].append(s-1)
q=[(0,[val[0]])]
ans=[0]*n
ans[0]=1
while q:
	cur,tab=q.pop()
	for nxt in con[cur]:
		if not ans[nxt]:
			if tab[-1]<val[nxt]:
				q.append((nxt,tab+[val[nxt]]))
				ans[nxt]=ans[cur]+1
			else:
				tab[bisect_left(tab,val[nxt])]=val[nxt]
				q.append((nxt,tab))
				ans[nxt]=ans[cur]
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = 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
                heapq.heappush(q, (dist[j], j))
    return dist


sys.setrecursionlimit(20000000)


def main():
    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())
        if A[v - 1] - A[u - 1] > 0:
            edge[u - 1].append((1, v - 1))
        else:
            edge[u - 1].append((10 ** 9, v - 1))
        if A[u - 1] - A[v - 1] > 0:
            edge[v - 1].append((1, u - 1))
        else:
            edge[v - 1].append((10 ** 9, u - 1))
    D = dijkstra(0, N, edge)
    for d in D:
        print(d % (10 ** 9) + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

####
from bisect import bisect_left
def solve(N, A, graph):
    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:
def main():
    from collections import deque
    import sys
    import bisect
    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 = [-1 for _ in range(n)]
    memo = [[] for _ in range(n)]
    que = deque()
    que.append(0)
    memo[0] = [a[0]]
    d[0] = 1

    while len(que):
        cur = que.popleft()
        for to in edges[cur]:
            if d[to] == -1:
                memo[to] = memo[cur]
                if memo[cur][-1] < a[to]:
                    d[to] = d[cur] + 1
                    memo[to].append(a[to])
                else:
                    d[to] = d[cur]
                    memo[to][bisect.bisect_left(memo[to], a[to])] = a[to]
                que.append(to)
        memo[cur] = []

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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


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())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

    
def dfs(vs, lis, lis_len):
    
    if lis[-1] < a[vs]:
        lis.append(a[vs])
    else:
        index = bisect_left(lis, a[vs])
        lis[index] = a[vs]
    
    lis_len[vs] = len(lis)-1
    
    
    for ve in edge[vs]:
        if len(edge[vs])>=3:
            lis = copy.copy(lis)
        if lis_len[ve] == -1:
            lis_len = dfs(ve, lis, lis_len)
    return lis_len


ans = dfs(0,[0],[-1]*n)
print("\n".join(map(str,ans)))

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:
                if A[i] < A[j]:
                    cnt_j = cnt + 1
                    if M < cnt_j:
                        M_j = cnt_j
                    else:
                        M_j = M

                    if M_j > res[j]:
                        res[j] = M_j
                    heapq.heappush(q, (dist[j], j, cnt_j, M_j))

            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:
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:
            
            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:
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()
    count = 0
    for next in g[now]:
        if ans[next] == None:
            count += 1
    if False:
        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:
                    next_l = now_l[:]
                    next_l[bisect.bisect_left(now_l, a[next])] = a[next]
                    q.append((next, next_l))
                    ans[next] = len(now_l)

    else:
        for next in g[now]:
            if ans[next] == None:
                if a[next] > now_l[-1]:
                    now_l.append(a[next])
                    q.append((next, now_l))
                    ans[next] = len(now_l)
                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:
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

N = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * N
ans = [0] * N

def dfs(v, p):
    i = bisect_left(lis, a[v])
    ans[v] = i + 1
    tmp = lis[i]
    lis[i] = a[v]
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
    lis[i] = tmp

dfs(0, -1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
# input=sys.stdin.readline
from collections import deque
import heapq
from itertools import combinations
import bisect

n=int(input())
a=list(map(int,input().split()))
g=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    u-=1
    v-=1
    g[u].append(v)
    g[v].append(u)
# pa=[-1]*n
# v=[-1]*n
# q=deque([0])
# v[0]=1
# while q:
#     p=q.popleft()
#     for i in g[p]:
#         if v[i]==-1:
#             pa[i]=p
#             v[i]=1
#             q.append(i)
v=[0]*n
d=[[] for i in range(n)]
q=deque([0])
v[0]=1
d[0].append(a[0])
while q:
    p=q.pop()
    for i in g[p]:
        if v[i]==0:
            v[i]=1
            if d[p][-1]<a[i]:
                d[i]=d[p]+[a[i]]
            else:
                bi=bisect.bisect_left(d[p],a[i])
                d[p][bi]=a[i]
                d[i]=d[p]
            q.append(i)
for i in range(n):
    print(len(d[i]))

Submission status: Wrong Answer

Solution code:
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = 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
                heapq.heappush(q, (dist[j], j))
    return dist


sys.setrecursionlimit(20000000)


def main():
    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())
        if A[v - 1] - A[u - 1] > 0:
            edge[u - 1].append((1, v - 1))
        else:
            edge[u - 1].append((0, v - 1))
        if A[u - 1] - A[v - 1] > 0:
            edge[v - 1].append((1, u - 1))
        else:
            edge[v - 1].append((0, u - 1))
    D = dijkstra(0, N, edge)
    for d in D:
        print(d + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
from bisect import bisect_left
n=int(input())
*a,=map(int,input().split())
st=[list(map(int,input().split())) for _ in range(n-1)]
con=[[] for _ in range(n)]
val=[i<<30+x for i,x in enumerate(a)]
for s,t in st:
	con[s-1].append(t-1)
	con[t-1].append(s-1)
q=[(0,[val[0]])]
ans=[0]*n
while q:
	cur,tab=q.pop()
	ans[cur]=len(tab)
	for nxt in con[cur]:
		if not ans[nxt]:
			if tab[-1]<val[nxt]:
				q.append((nxt,tab+[val[nxt]]))
			else:
				tab[bisect_left(tab,val[nxt])]=val[nxt]
				q.append((nxt,tab))
print("\n".join(map(str,ans)))

Submission status: Wrong Answer

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, deque
from sys import exit
import math
import copy
from bisect import bisect_left

import sys
sys.setrecursionlimit(1000000)

def calc(arr, query):
    ret = 0
    # print(arr)\
    for q in query:
        if arr[q[1] - 1] - arr[q[0] - 1] == q[2]:
            ret += q[3]

    return ret

def dfs(tree, nums, answers, current, LIS, visited):
    # if current >= 7:
        # print(current, LIS)
    visited[current] = 1
    nc = nums[current]
    if nc > LIS[-1]:
        LIS.append(nc)
    else:
        ins = bisect_left(LIS, nc)
        if LIS[ins] != nc:
            if ins == 0:
                LIS[ins] = nc
            elif LIS[ins-1] != nc:
                LIS[ins] = nc
    answers[current] = len(LIS)
    # 分岐するときはLIS複製
    # そうでなければポインタ私
    if len(tree[current]) == 1:
        return
    if len(tree[current]) == 2 and current != 0:
        for nx in tree[current]:
            if not visited[nx]:
                dfs(tree, nums, answers, nx, LIS, visited)
        return
    else:
        org = LIS
        # print("bunki", current)
        for nx in tree[current]:
            if not visited[nx]:
                LIScp = copy.copy(org)
                dfs(tree, nums, answers, nx, LIScp, visited)

        return



def main():
    n = getN()
    nums = getList()
    tree = [[] for _ in range(n)]
    for i in range(n - 1):
    # start, end, cost
        a, b = getList()
        # 0-indexed
        a -= 1
        b -= 1
        tree[a].append(b)
        tree[b].append(a)

    # print(tree)
    answers = [0 for i in range(n)]
    answers[0] = 1
    LIS = [nums[0]]
    visited = [0 for i in range(n)]
    visited[0] = 1
    dfs(tree, nums, answers, 0, LIS, visited)

    for ans in answers:
        print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
a_list = list(map(int,input().split()))
v_list = [list(map(int,input().split())) for _ in range(n-1)]

node_dict = {}

for elem in v_list:
    parent = a_list[elem[0]-1]
    child = a_list[elem[1]-1]
    if elem[0] not in node_dict:
        node_dict[elem[0]] = [parent]
    node_dict[elem[1]] = {}
    target_list = node_dict[elem[0]].copy()
    if target_list[-1] < child:
        target_list.append(child)
    else:
        target_list[bisect.bisect_left(target_list,child)] = child
    node_dict[elem[1]] = target_list


for k in node_dict:
    print(len(node_dict[k]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

ans = [0] * N
dp = [INF] * (N+10)

def dfs(now, par):
    ng = -1
    ok = N+5
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if A[now] < dp[mid]:
            ok = mid
        else:
            ng = mid
    memo = dp[ok]
    dp[ok] = A[now]
    ng1 = 0
    ok1 = N+5
    while ok1 - ng1 > 1 :
        mid = (ok1 + ng1) // 2
        if dp[mid] == INF:
            ok1 = mid
        else:
            ng1 = mid
    ans[now] = ok1

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now)
    dp[ok] = memo


dfs(0, -1)

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

Submission status: Wrong Answer

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7
# MOD = 998244353


N = read_item()
vals = read_n_item()
graph = defaultdict(list)

for _ in range(N-1):
    u, v = read_n_item()
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)


ans = [0] * N
ans[0] = 1
dp = [float('inf')] * (N+1)
dp[0] = vals[0]


def dfs(cur, pre):
    # print(dp)
    for child in graph[cur]:
        if child == pre:
            continue
        i = bisect_left(dp, vals[child])
        ans[child] = i+1

        temp = dp[i]
        dp[i] = vals[child]
        dfs(child, cur)
        dp[i] = temp

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

Submission status: Wrong Answer

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

INF = float('inf')

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

dp = [-INF]
anss = [0] * N
def dfs(vNow, vPar):
    A = As[vNow]
    if dp[-1] < A:
        dp.append(A)
    else:
        i = bisect_left(dp, A)
        dp[i] = A
    anss[vNow] = len(dp)-1
    L = len(dp)
    V = dp[-1]
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)
#        print('v2:', v2, '/ len(dp):', len(dp), '/ L:', L)
        if len(dp) > L:
            dp.pop()
        else:
            dp[-1] = V

dfs(0, -1)

print('\n'.join(map(str, anss)))

Submission status: Wrong Answer

Solution code:


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

from bisect import bisect_left
 
l = [a[0]]
# for a in A[1:]:
#     if a > L[-1]:
#         # Lの末尾よりaが大きければ増加部分列を延長できる
#         L.append(a)
#     else:
#         # そうでなければ、「aより小さい最大要素の次」をaにする
#         # 該当位置は、二分探索で特定できる
#         L[bisect_left(L, a)] = a
# return len(L)

q = [(0, -1, l, None, None)]
ans = [None] * n
while q:
    u, prev, lst, old, ind = q.pop()
    ans[u] = len(lst)
    if old is not None:
        lst[ind] = old
    for v in ns[u]:
        if prev==v:
            continue
        aa = a[v]
        if aa > lst[-1]:
            tmp = lst + [aa]
            old = None
            ind = None
        else:
            tmp = lst
            ind = bisect_left(lst, aa)
            old = lst[ind]
            lst[ind] = aa
#         print(tmp)
        q.append((v, u, tmp, old, ind))
print("\n".join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
import heapq


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


def dijkstra(start, n_nodes, edge):
    dist = [float("inf")] * n_nodes
    dist[start] = 0
    # 優先度キューの準備
    q = [(dist[start], start)]
    heapq.heapify(q)
    while q:
        # スタートから最も最短距離のものを取り出す
        d, i = 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
                heapq.heappush(q, (dist[j], j))
    return dist


sys.setrecursionlimit(20000000)


def main():
    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())
        if A[v - 1] - A[u - 1] > 0:
            edge[u - 1].append((1, v - 1))
        else:
            edge[u - 1].append((0, v - 1))
        if A[u - 1] - A[v - 1] > 0:
            edge[v - 1].append((1, u - 1))
        else:
            edge[v - 1].append((0, u - 1))
    D = dijkstra(0, N, edge)
    for d in D:
        print(d + 1)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

N = int(input())
a = [0] + list(map(int, input().split()))
G = [[] for _ in range(N+1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * (N+1)
ans = [0] * (N+1)

def dfs(v, p):
    i = bisect_left(lis, a[v])
    ans[v] = i + 1
    tmp = lis[i]
    lis[i] = a[v]
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
    lis[i] = tmp

dfs(1, 0)
print('\n'.join(map(str, ans[1:])))

Submission status: Wrong Answer

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

INF = float('inf')

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

dp = [-INF]
anss = [0] * N
def dfs(vNow, vPar):
    A = As[vNow]
    if dp[-1] < A:
        dp.append(A)
    else:
        i = bisect_left(dp, A)
        dp[i] = A
    anss[vNow] = len(dp)-1
    L = len(dp)
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)
#        print('v2:', v2, '/ len(dp):', len(dp), '/ L:', L)
        if len(dp) > L:
            dp.pop()

dfs(0, -1)

print('\n'.join(map(str, anss)))