Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices, whose i-th edge connects Vertex u_i and Vertex v_i.
Vertex i has an integer a_i written on it.
For every integer k from 1 through N, solve the following problem:

We will make a sequence by lining up the integers written on the vertices along the shortest path from Vertex 1 to Vertex k, in the order they appear. Find the length of the longest increasing subsequence of this sequence.

Here, the longest increasing subsequence of a sequence A of length L is the subsequence A_{i_1} , A_{i_2} , ... , A_{i_M} with the greatest possible value of M such that 1 \leq i_1 < i_2 < ... < i_M \leq L and A_{i_1} < A_{i_2} < ... < A_{i_M}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i \leq 10^9

1 \leq u_i , v_i \leq N

u_i \neq v_i

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N
u_1 v_1
u_2 v_2
:
u_{N-1} v_{N-1}

Output

Print N lines. The k-th line, print the length of the longest increasing subsequence of the sequence obtained from the shortest path from Vertex 1 to Vertex k.

Sample Input 1

10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10

Sample Output 1

1
2
3
3
4
4
5
2
2
3

For example, the sequence A obtained from the shortest path from Vertex 1 to Vertex 5 is 1,2,5,3,4. Its longest increasing subsequence is A_1, A_2, A_4, A_5, with the length of 4.



Sample input:
10
1 2 5 3 4 6 7 3 2 4
1 2
2 3
3 4
4 5
3 6
6 7
1 8
8 9
9 10


Sample output:
1
2
3
3
4
4
5
2
2
3

Submission status: Wrong Answer

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # f([3, 5, 2, 4, 6])
    N = int(input())
    A = [int(a) for a in input().split()]
    uv = [
        [int(a) for a in input().split()]
        for _ in range(N - 1)
    ]

    uv = [
        sorted(a) for a in uv
    ]
    # print(uv)

    notleaf = set()
    parent_table = dict()

    for u, v in uv:
        parent_table[v] = u
        notleaf.add(u)

    result = dict()
    result[1] = [1]

    def f(path):
        if path[-1] in result:
            return
        f(path[:-1])

        DP = result[path[-2]]

        maxindex = len(DP) - 1

        ind = path[-1]
        elem = A[ind - 1]
        for j in range(maxindex, -1, -1):
            if DP[j] < elem:
                if len(DP) == j + 1:
                    result[ind] = DP + [elem]
                    return
                if elem < DP[j + 1]:
                    DDD = [a for a in DP]
                    DDD[j + 1] = elem
                    result[ind] = DDD
                    return
        result[ind] = [a for a in DP]

    def get_path(index):
        if index == 1:
            return [1]
        return get_path(parent_table[index]) + [index]

    # for i in range(1, N + 1):
    #     if i in notleaf:
    #         continue
    #     p = get_path(i)
        # f(p)
    # for i in range(N):
    #     print(len(result[i+1] or [] ))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1
#print(AA, a2f)

ss = SegTree([0]*(N+1), N+1, -1, max)
R = [0]*(N+1)
R[1] = 1
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        parent = path[-1]
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)+1
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
a2i = dict()
d = dict()
rj = 0
for j, (i, a) in enumerate(iA):
    a2i[a] = j
    if a not in d:
        rj = j
    d[a] = rj
AA = [0]*(N+1)
a2f = [0]*(N+1)
for i in range(N+1):
    AA[i] = a2i[A[i]]
    a2f[i] = d[A[i]]
#print(AA, a2f)

ss = SegTree([0]*(N+1), N+1, -1, max)
R = [0]*(N+1)
R[1] = 1
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        parent = path[-1]
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)+1
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Wrong Answer

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

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

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

ans = [0] * N
ans[0] = 1
def dfs(node, par, root, dp):
  global ans
  children = tree[node]
  if len(children) >= 3:
    _root = node
    dp = [A[node]]
  else:
    _root = root
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    ans[child] = ans[_root] + idx
    if idx == len(dp):
      dfs(child, node, _root, dp+[num])
    else:
      dp[idx] = num
      dfs(child, node, _root, dp)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
As = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(N-1)]

history = []
stack = [1]
lis = [1] * N 

while stack:
    pos = stack.pop()
    if history:
        for i in range(len(history)-1, -1, -1):
            if (history[i], pos) in edges or (pos, history[i]) in edges:
                history = history[:i+1]
                history.append(pos)
                break
    else:
        history.append(pos)
    for u, v in edges:
        if u == pos:
            if not v in history:
                stack.append(v)
        elif v == pos:
            if not u in history:
                stack.append(u)
    for h in history[::-1]:
        if As[h-1] < As[pos-1]:
            lis[pos-1] = lis[h-1] + 1
            break

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

Submission status: Wrong Answer

Solution code:
import bisect
import sys
sys.setrecursionlimit(200000)

"""
seq=[1,5,23,6,43,21,7,3,34]

LIS = [seq[0]]
for i in range(len(seq)):
    if seq[i] > LIS[-1]:
        LIS.append(seq[i])
    else:
        LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]

print(len(LIS))
"""

n=int(input())
val=[0]
val.extend([int(i) for i in input().split()])
tree=[[] for i in range(n+1)]

for i in range(n-1):
    a,b=map(int,input().split())
    tree[min(a,b)].append(max(a,b))

stc=[[0]]
res=[-1 for i in range(n+1)]

def saiki(go):
    now=stc[-1][:]
    #print(go,"now=",now)
    if val[go]>now[-1]:
        now.append(val[go])
    else:
        now[bisect.bisect_left(now, val[go])] = val[go]
    res[go]=len(now)
    #print(stc)
    stc.append(now[:])
    #print("addd",stc)
    
    for nex in tree[go]:
        saiki(nex)
    stc.pop()
    #print("popd",stc)
    return

saiki(1)
#print(res)

for ele in res[1:]:
    print(ele-1)

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
INT_MAX = 10**9
# 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 = [vals[0]]


def dfs(cur, pre):
    # ans[cur] = len(dp)

    for nxt in graph[cur]:
        if nxt == pre:
            continue
        i = bisect_left(dp, vals[nxt])
        ans[nxt] = i + 1
        if i < len(dp):
            temp = dp[i]
            dp[i] = vals[nxt]
            dfs(nxt, cur)
            dp[i] = temp
        else:
            dp.append(vals[nxt])
            dfs(nxt, cur)
            dp.pop()


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    def dfs(x):
        ans[x] = bisect_right(dp, a[x])
        for e in edg[x]:
            if d[e]:
                d[e] = 0
                i = bisect_right(dp, a[e])
                p = dp[i]
                dp[i] = a[e]
                dfs(e)
                dp[i] = p
    n = II()
    a = LI()
    dp = [inf] * n
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        u, v = LI_()
        edg[u].append(v)
        edg[v].append(u)
    d = [1] * n
    ans = [1] * n
    d[0] = 0
    dp[0] = a[0]
    dfs(0)
    for a in ans:
        print(a)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def dijkstra(n, graph, s):
    dist = [float('inf')] * n
    hq = [(0, s, 0)] # (dist, before_node, tmp_count)
    dist[s] = 0 # [cost, ans]
    ans = [0] * n
    ans[0] = 1
    while hq:
        c, v, tmp = heappop(hq)
        if dist[v] < c:
            continue
        for t, cost in graph[v]:
            if dist[v] + cost <= dist[t]:
                dist[t] = dist[v] + cost
                if A[t] > A[v]:
                    ans[t] = max(ans[v], tmp+1)
                    heappush(hq, (dist[t], t, tmp+1))
                else:
                    ans[t] = ans[v]
                    heappush(hq, (dist[t], t, 1))
    return ans

N = int(input())
A = tuple(map(int, input().rstrip().split()))
graph = [[] for _ in range(N)]
for i in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    graph[u].append((v, 1))
    graph[v].append((u, 1))
ans = dijkstra(N, graph, 0)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

N = int(input())

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

F = [-1 for _ in range(N)]
F[0] = 1
INF = 10 ** 9
dp = [INF for _ in range(N + 1)]


def dfs(s):
    for d in T[s]:
        if F[d] == -1:
            t = bisect.bisect_left(dp, A[d])
            p = dp[t]
            dp[t] = A[d]
            F[d] = bisect.bisect_left(dp, INF) + 1
            dfs(d)
            dp[t] = p


dfs(0)

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

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
visited = [False] * N

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

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

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
a2i = dict()
d = dict()
rj = 0
for j, (i, a) in enumerate(iA):
    a2i[a] = j
    if a not in d:
        rj = j
    d[a] = j
AA = [0]*(N+1)
a2f = [0]*(N+1)
for i in range(N+1):
    AA[i] = a2i[A[i]]
    a2f[i] = d[A[i]]
#print(AA, a2f)

ss = SegTree([0]*(N+1), N+1, -1, max)
R = [0]*(N+1)
R[1] = 1
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        parent = path[-1]
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)+1
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Wrong Answer

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
a2i = dict()
d = dict()
rj = 0
for j, (i, a) in enumerate(iA):
    a2i[a] = j
    if a not in d:
        rj = j
    d[a] = j
AA = [0]*(N+1)
a2f = [0]*(N+1)
for i in range(N+1):
    AA[i] = a2i[A[i]]
    a2f[i] = d[A[i]]
print(AA, a2f)

ss = SegTree([0]*(N+1), N+1, -1, max)
R = [0]*(N+1)
R[1] = 1
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        parent = path[-1]
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)+1
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[i])

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
stack = []

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from heapq import heappush, heappop
def dijkstra(n, graph, s):
    dist = [float('inf')] * n
    hq = [(0, s, 0)] # (dist, before_node, tmp_count)
    dist[s] = 0 # [cost, ans]
    ans = [0] * n
    ans[0] = 1
    while hq:
        c, v, tmp = heappop(hq)
        if dist[v] < c:
            continue
        for t, cost in graph[v]:
            if dist[v] + cost <= dist[t]:
                dist[t] = dist[v] + cost
                if A[t] > A[v]:
                    ans[t] = max(ans[v]+1, tmp+1)
                    heappush(hq, (dist[t], t, tmp+1))
                else:
                    ans[t] = ans[v]
                    heappush(hq, (dist[t], t, 1))
    return ans

N = int(input())
A = tuple(map(int, input().rstrip().split()))
graph = [[] for _ in range(N)]
for i in range(N-1):
    u, v = map(lambda x: int(x)-1, input().split())
    graph[u].append((v, 1))
    graph[v].append((u, 1))
ans = dijkstra(N, graph, 0)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
def LIS(L,n):
  res=0
  dp=[1]*n
  for i in range(n):
    for j in range(i):
      if L[j]<L[i]:
        dp[i]=max(dp[i],dp[j]+1)
    res=max(res,dp[i])
  return res
 
n=int(input())
a=list(map(int,input().split()))
parent=[0]*n
root=[[a[i]] for i in range(n)]
for i in range(n-1):
    l=list(map(int,input().split()))
    parent[l[1]-1]=l[0]-1
for i in range(n):
    c=parent[i]
    while(c!=0):
        if not root[c]:
            root[i].extend([a[c]])
            c=parent[c]
        else:
            root[i].extend(root[c])
            break

#頂点0からの最短経路
print(1)
for i in range(1,n):
    root[i].extend([1])
    root[i].reverse()
    res=LIS(root[i],len(root[i]))
    print(res)

Submission status: Wrong Answer

Solution code:
import math
from bisect import bisect_left
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())
    g[u-1].append(v-1)


parent = [''] * n
def bfs(G,start):
    from collections import deque
    dist = [-1] * n
    
    dist[start] = 0
    q = deque([start])
    add,pop=q.append,q.popleft
    while q:
        v = pop()
        for nv in G[v]:
            if dist[nv] < 0:
                dist[nv] = dist[v]+1
                parent[nv] += str(parent[v])+str(nv)
                add(nv)
            # 2部グラフ判定
            # else:
            #     if dist[v]%2 == dist[nv]%2:
            #         is_bipartite = False
    return dist

def lis(A: list):
    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)

dit = bfs(g,0)
for i in range(n):
    parent[i] = '0'+parent[i]
    l = []
    for j in range(len(parent[i])):
        ix = int(parent[i][j])
        l.append(a[ix])
    print(lis(l))


# for i in range(n):
#     parent[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
INT_MAX = 10**9
# 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 = [vals[0]]


def dfs(cur, pre):
    # print(f'cur: {cur}')
    for nxt in graph[cur]:
        if nxt == pre:
            continue
        i = bisect_left(dp, vals[nxt])
        ans[nxt] = i+1
        if i < len(dp):
            temp = dp[i]
            dp[i] = vals[nxt]
            dfs(nxt, cur)
            dp[i] = temp
        else:
            dp.append(vals[nxt])
            dfs(nxt, cur)
            dp.pop()


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

Submission status: Wrong Answer

Solution code:
import queue
import bisect
INF = 10**10
N = int(input())
A = list(map(int,input().split()))
adj = [[] for _ in range(N)]
#print (adj)
for n in range(N-1):
    u, v = map(int,input().split())
    u-=1
    v-=1
    adj[u].append(v)
    adj[v].append(u)
#print (adj)

lis = [INF] * N
ans = [INF] * N
ans[0] = 1
q = queue.Queue()
q.put((0,-1,lis,[],[])) # スタート地点をenqueue
while(not q.empty()):
    cur, par, lis, his, X = q.get()
    i = bisect.bisect(lis, A[cur]) # 更新すべき最小値
    lis = lis[:]
    X = X+[i]
    
    lis[i] = A[cur]
    leaf = True
    for next in adj[cur]:
        if next != par:
            # his = his[:]
            # his.append(next)
            q.put((next,cur,lis, his+[next], X))
            leaf = False
    if leaf:
        #print (cur,lis,his,X)
        for i in range(len(his)):
            #print (his[i],lis[i],X[i+1])
            ans[his[i]] = X[i+1]+1
for a in ans:
    print (a)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
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

def dfs(now, par, len):
    ok = bisect.bisect_right(dp, A[now])
    memo = dp[ok]
    dp[ok] = A[now]

    ok1 = bisect.bisect_left(dp, INF)
    ans[now] = ok1

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

dfs(0, -1, 0)

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

Submission status: Wrong Answer

Solution code:

import heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
from bisect import bisect
from functools import lru_cache


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

si = lambda: input().strip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
msi = lambda: map(str, input().split())
lmii = lambda: list(map(int, input().split()))
lmsi = lambda: list(map(str, input().split()))
smii = lambda: sorted(map(int, input().split()))

# ----------

N = ii()
A = lmii()

ans = defaultdict(int)
tree = defaultdict(list)
for i in range(N-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)


def LIS(L):
    from bisect import bisect
    seq=[]
    for i in L:
        pos=bisect(seq,i)
        if len(seq)<=pos:
            seq.append(i)
        else:
            seq[pos]=i
    return len(seq)


def dfs(v, parent, path):
    global ans
    ans[v] = LIS(path)
    for to in tree[v]:
        if to == parent:
            continue
        path.append(A[to])
        dfs(to, v, path)
        path.pop(-1)

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

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N=int(input())
alist=[0]+list(map(int,input().split()))

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

def LIS(path,seq):
  import bisect  
  LIS=[seq[0]]
  
  for ii in range(10**9):
    if not path[ii] in answer_dic:
      break
  if ii>0:
    LIS=seq_dic[path[ii-1]]
  
  for i in range(ii,len(seq)):
    if seq[i] > LIS[-1]:
      LIS.append(seq[i])
    else:
      LIS[bisect.bisect_left(LIS, seq[i])]=seq[i]
    #print(i,seq[i],len(LIS))
    answer_dic[path[i]]=len(LIS)
    seq_dic[path[i]]=list(LIS)
   
  return LIS
      
def dfs(u,path,ls):    
  visited[u]=True
  #print(u,ls)
  #answer_dic[u]=ls

  cnt=0
  for v in graph[u]:
    if not visited[v]:
      dfs(v,path+[v],ls+[alist[v]])
      cnt+=1
      
  if cnt==0:
    #compute LIS of ls
    #print(u,ls)
    LIS(path,ls)
    #print(LIS(ls))

visited=[False]*(N+1)
answer_dic={}
seq_dic={}
dfs(1,[1],[alist[1]])
#print(answer_dic)

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

Submission status: Wrong Answer

Solution code:
N = int(input())
A = list(map(int,input().split()))
A = [0] + A
graph = {i+1:[] for i in range(N)}
for _ in range(N-1):
  u,v = map(int,input().split())
  graph[u].append(v)
  graph[v].append(u)
  
from collections import deque

queue = deque([(1,0,[],0)])

score = {i:0 for i in range(N+1)}

while queue:
  node, parent, path, lis = queue.popleft()
  
  if path ==[]:
    lis = 1
  elif A[node] > path[-1]:
    lis += 1
  else:
    lis = 1
  #path.append(A[node])
  score[node] = max(score[parent], lis)
  #print(node, path ,lis)
  for n in graph[node]:
    if n==parent:
      continue
    queue.append((n, node, path+[A[node]], lis))

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

Submission status: Wrong Answer

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

from collections import deque
G=[[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

B=[1]*n
temp=[1]*n
ongoing=[1]*n
queue = deque([0])
visited= [0]*n
while queue:
    a = queue.popleft()
    visited[a] = 1
    for i in G[a]:
        if visited[i] == 0:
            if A[i]>A[a]:
                ongoing[i]=ongoing[a]+1
            temp[i]=max(temp[a],ongoing[i])
            queue.append(i) 


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