Problem:


Score : 600 points

Problem Statement

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

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

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

Constraints

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

1 \leq a_i \leq 10^9

1 \leq u_i , v_i \leq N

u_i \neq v_i

The given graph is a tree.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

1
2
3
3
4
4
5
2
2
3

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



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


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

Submission status: Wrong Answer

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


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


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

    Q = deque()
    Q.append(1)
    parent = [-1] * (N + 1)
    parent[1] = 0
    ans = [0] * (N + 1)
    while Q:
        nv = Q.popleft()
        # DPs[nv] = DPs[parent[nv]].copy()
        pv = parent[nv]
        print(pv, ans[pv])
        t = bisect(DPs[pv][:ans[pv]], A[nv - 1])
        for i, a in enumerate(DPs[pv]):
            if a is None:
                break
            else:
                DPs[nv][i] = a
        # print(nv, t)
        DPs[nv][t] = A[nv - 1]
        if t >= ans[pv]:
            ans[nv] = ans[parent[nv]] + 1
        else:
            ans[nv] = ans[parent[nv]]

        for kouho in edges[nv]:
            if parent[kouho] == -1:
                Q.append(kouho)
                parent[kouho] = nv

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


if __name__ == '__main__':
    main()

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 = [INT_MAX] * N
dp[0] = 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

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


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

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=LI()
    adj=[[]for _ in range(N)]
    
    for i in range(N-1):
        u,v=MI()
        u-=1
        v-=1
        adj[u].append(v)
        adj[v].append(u)
        
    dp=[[0,0]for _ in range(N)]
    #dp[i]は点iの最小LISの[長さ，末尾]
    dp[0]=[1,a[0]]
    
    st=[]
    st.append((0,-1))#v,p
    
    from collections import defaultdict
    dd = defaultdict(int)
    #末尾の数字ごとに
    
    while not st==[]:
        v,p=st.pop()
        for nv in adj[v]:
            if nv!=p:
                aaa=dp[v][0]#長さ
                bbb=dp[v][1]#値
                if a[nv]>bbb:
                    dp[nv][0]=aaa+1
                    dp[nv][1]=a[nv]
                    st.append((nv,v))
                else:
                    dp[nv][0]=aaa
                    dp[nv][1]=a[nv]
                    st.append((nv,v))
                    
                    
    for i in range(N):
        print(dp[i][0])
                    
                
        
    

main()

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] = max(ans[v], 1)
                    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
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    a=LI()
    adj=[[]for _ in range(N)]
    
    for i in range(N-1):
        u,v=MI()
        u-=1
        v-=1
        adj[u].append(v)
        adj[v].append(u)
        
    dp=[[0,0]for _ in range(N)]
    #dp[i]は点iの最小LISの[長さ，末尾]
    dp[0]=[1,a[0]]
    
    st=[]
    st.append((0,-1))#v,p
    
    from collections import defaultdict
    dd = defaultdict(int)
    #末尾の数字ごとに
    
    while not st==[]:
        v,p=st.pop()
        for nv in adj[v]:
            if nv!=p:
                aaa=dp[v][0]#長さ
                bbb=dp[v][1]#値
                if a[nv]>bbb:
                    dp[nv][0]=aaa+1
                    dp[nv][1]=a[nv]
                    st.append((nv,v))
                else:
                    dp[nv][0]=aaa
                    dp[nv][1]=a[nv]
                    st.append((nv,v))
                    
                    
    for i in range(N):
        print(dp[i][0],dp[i][1])
                    
                
        
    

main()

Submission status: Wrong Answer

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

from bisect import bisect_left

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

INF = 10 ** 10

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

arrived = [False] * n

ans = [None] * n
ans[0] = 1

dp = [INF] * n


def dfs(u):
    arrived[u] = True
    for v in adj[u]:
        if not arrived[v]:
            idx = bisect_left(dp, a[v])
            tmp = dp[idx]
            dp[idx] = a[v]
            ans[v] = idx + 1
            dfs(v)
            dp[idx] = tmp


dp[0] = a[0]
dfs(0)
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
a=list(map(int,input().split()))
s=[[]for i in range(N)]
for i in range(N-1):
    c,b=map(lambda x: int(x)-1,input().split())
    s[c].append(b)
    s[b].append(c)
l=[0]*N
sys.setrecursionlimit(300000)
l[0]=1
def hu(n,d):
    for i in s[n]:
        if not l[i]:
            k=[min(d[0],a[i])]
            for j in range(1,len(d)):
                if d[j-1]<a[i]<d[j]:
                    k.append(a[j])
                else:
                    k.append(d[j])
            if d[-1]<a[i]:
                k.append(a[i])
            l[i]=len(k)
            hu(i,k)
hu(0,[a[0]])
print(*l)

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=[[] 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):
        root[i].extend([a[c]])
        c=parent[c]

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

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, lis):
    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)
    lis[i] = tmp

dfs(0, -1, lis)
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:
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
dp = []
def dfs(node, par, dp):
  global ans
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    if idx == len(dp):
      _dp = dp.copy() + [num]
      ans[child] = idx + 1
      dfs(child, node, _dp)
    else:
      _dp = dp.copy()
      _dp[idx] = num
      ans[child] = idx + 1
      dfs(child, node, _dp)

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

Submission status: Wrong Answer

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

from bisect import bisect_left

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

INF = 10 ** 10

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

arrived = [False] * n

ans = [None] * n
ans[0] = 1

dp = [INF] * n


def dfs(u):
    arrived[u] = True
    for v in adj[u]:
        if not arrived[v]:
            idx = bisect_left(dp, a[v])
            tmp = dp[idx]
            dp[idx] = min(dp[idx], a[v])
            ans[v] = idx + 1
            dfs(v)
            dp[idx] = tmp


dp[0] = a[0]
dfs(0)
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
al = list(map(int,input().split()))

from collections import defaultdict
G = defaultdict(list)

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

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

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


dfs(0, dp)
flag = False
for i in range(n):
    print(ansl[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()
for j, (i, a) in enumerate(iA):
    a2i[a] = j
    if a not in d:
        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:
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] = max(ans[v], tmp)
                    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 heapq
from collections import defaultdict, deque
from math import ceil, factorial, gcd
from itertools import accumulate, permutations
import sys
from bisect import bisect

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

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
n = int(input())
al = list(map(int,input().split()))

from collections import defaultdict
G = defaultdict(list)

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

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

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


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

Submission status: Wrong Answer

Solution code:
import math
import collections
def solve(n, values, edge):
    dic = collections.defaultdict(set)
    for a, b in edge:
        dic[a-1].add(b-1)
        dic[b-1].add(a-1)
    ans = [1]*n
    seen = {0}
    bfs = collections.deque([(0, 1)])
    while bfs:
        node, path = bfs.popleft()
        for i in range(n):
            if 1<<i & path and value[i]<value[node]:
                ans[node] = max(ans[node], ans[i]+1)
        for nei in dic[node]:
            if nei not in seen:
                seen.add(nei)
                bfs.append((nei, path|1<<nei))
                    
    return ans

n = int(input())
value = list(map(int, input().split()))
edge = []
for _ in range(n-1):
    a, b = map(int, input().split())
    edge.append([a, b])
ans = solve(n, value, edge)
for n in ans:
    print(n)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    Aorder = [(A[i], i) for i in range(N)]
    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)
    Ans = [1] * N
    q = deque()
    nd = dict()
    nd[1] = A[0]
    for nextn in Edge[0]:
        q.append((nextn, 0, nd, 1))
    
    while q:
        nn, pre, cd, mL = q.popleft()
        low, high = 0, mL + 1
        while high - low > 1:
            mid = (low + high)// 2
            if cd[mid] >= A[nn]: high = mid
            else: low = mid
        Ans[nn] = high
        cd[high] = A[nn]
        for nextn in Edge[nn]:
            if nextn != pre:
                if high == mL + 1: q.append((nextn, nn, cd, mL + 1))
                else: q.append((nextn, nn, cd, mL))
    print("\n".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

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()
for j, (i, a) in enumerate(iA):
    a2i[a] = j
    if a not in d:
        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 += [-u, u]
    else:
#        child = path.pop()
#        ss.update(AA[child], 0)
        ss.update(AA[-v], 0)
for i in range(1, N+1):
    print(R[i])

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] = max(ans[v], tmp)
                    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 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[:])
    
    for nex in tree[go]:
        saiki(nex)
    stc.pop()
    #print("popd")
    return

saiki(1)
#print(res)

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

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    A = [int(a) for a in input().split()]
    Aorder = [(A[i], i) for i in range(N)]
    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)
    Ans = [1] * N
    q = deque()
    nd = dict()
    nd[1] = A[0]
    for nextn in Edge[0]:
        q.append((nextn, 0, nd, 1))
    
    while q:
        nn, pre, cd, mL = q.popleft()
        low, high = 0, mL + 1
        while high - low > 1:
            mid = (low + high)// 2
            if cd[mid] > A[nn]: high = mid
            else: low = mid
        Ans[nn] = high
        cd[high] = A[nn]
        for nextn in Edge[nn]:
            if nextn != pre:
                if high == mL + 1: q.append((nextn, nn, cd, mL + 1))
                else: q.append((nextn, nn, cd, mL))
    print("\n".join(map(str, Ans)))

    return 0

if __name__ == "__main__":
    solve()

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:
                if memo[cur][-1] < a[to]:
                    d[to] = d[cur] + 1
                    memo[to] = memo[cur] + [a[to]]
                else:
                    d[to] = d[cur]
                    memo[cur][bisect.bisect_left(memo[cur], a[to])] = a[to]
                    memo[to] = memo[cur]
                que.append(to)

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

if __name__ == '__main__':
    main()