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
import bisect


def dfs(edge):
    insert = bisect.bisect_left(lis_array, a_array[edge - 1])
    old = lis_array[insert]
    lis_array[insert] = a_array[edge - 1]
    ans_array[edge - 1] = insert + 1
    for next_edge in node_dic[edge]:
        if use_array[next_edge - 1] == -1:
            use_array[next_edge - 1] = 1
            dfs(next_edge)
    lis_array[insert] = old


sys.setrecursionlimit(10 ** 9)
N = int(input())
a_array = list(map(int, input().split()))

node_dic = {}
for _ in range(N - 1):
    u, v = map(int, input().split())
    if u in node_dic:
        node_dic[u].append(v)
    else:
        node_dic[u] = [v]

    if v in node_dic:
        node_dic[v].append(u)
    else:
        node_dic[v] = [u]

# print(node_dic)

use_array = [-1] * N
ans_array = [0] * N

INF = 2 * 10 ** 9
lis_array = [INF] * N

use_array[0] = 1
dfs(1)
print("\n".join(map(str, ans_array)))

Submission status: Wrong Answer

Solution code:
import sys
import heapq
def dijkstra(s, es):
    INF=sys.maxsize
    cs=[INF]*len(es)
    ss=[-1]*len(es)
    cs[s],hq=0,[]
    heapq.heapify(hq)
    heapq.heappush(hq,(cs[s],s))
    while hq:
        d,v=heapq.heappop(hq)
        if cs[v]<d:continue
        for t,c in es[v]:
            if cs[t]>cs[v]+c:
                cs[t]=cs[v]+c
                ss[t]=v
                heapq.heappush(hq,(cs[t],t))
    return cs,ss
def lis(a):
    n=len(a)
    dp=[1]*n
    for i in range(n):
        for j in range(i):
            if a[j]<a[i]:
                dp[i]=max([dp[i],dp[j]+1])
    return dp[-1]
def main():
    N=int(sys.stdin.readline().strip())
    a=list(map(int,sys.stdin.readline().split()))
    es=[[] for _ in [0]*N]
    for _ in [0]*(N-1):
        u,v=tuple(map(int,sys.stdin.readline().split()))
        u,v=u-1,v-1
        es[u].append((v,a[v]))
        es[v].append((u,a[u]))
    cs,ss=dijkstra(0,es)
    for i in range(N):
        j,p=i,[]
        while True:
            p=[a[j]]+p
            if ss[j]==-1:break
            j=ss[j]
        print(lis(p))
if __name__=='__main__':main()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

n = int(input())
a = [int(x) for x in input().split()]
g = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
    g[v - 1].append(u - 1)
from collections import defaultdict
d = defaultdict(list)
import bisect
from copy import deepcopy
def dfs(u):
    stack = [u]
    d[u] = [a[u]]
    used = [False]*n
    used[u] = True
    while stack:
        v = stack.pop()
        for i in g[v]:
            if used[i] == True:
                continue
            temp = deepcopy(d[v])
            # print(i, temp)
            if a[i] > temp[-1]:
                temp.append(a[i])
                d[i] = temp
                used[i] = True
                stack.append(i)
            else:
                idx = bisect.bisect_left(temp, a[i])
                temp = temp[:idx]
                temp.append(a[i])
                d[i] = temp
                used[i] = True
                stack.append(i)
dfs(0)
for i in range(n):
    print(len(d[i]))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
from collections import deque
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n=read()
a=list(reads())
formerls=[0 for i in range(n)]
count=[1]*n
lis=[]
for i in range(n-1):
  u,v=reads()
  u-=1
  v-=1
  formerls[v]=u
#print(formerls)
@lru_cache(None)
def dp(k):
   if k==0:
      return[a[0]]
   former=formerls[k]
   lis=dp(former)[:]
   #print(former,lis)
   if lis[-1]<a[k]:
     lis.append(a[k])
   else:
     lis[bisect.bisect_left(lis,a[k])]=a[k]
   return lis
for i in range(n):
  #print(dp(i))
  print(len(dp(i)))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
from functools import lru_cache
from collections import defaultdict
from collections import deque
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n=read()
a=list(reads())
formerls=[0 for i in range(n)]
count=[1]*n
lis=[]
for i in range(n-1):
  u,v=reads()
  u-=1
  v-=1
  formerls[v]=u
print(formerls)
@lru_cache(None)
def dp(k):
   if k==0:
      return[a[0]]
   former=formerls[k]
   lis=dp(former)[:]
   #print(former,lis)
   if lis[-1]<a[k]:
     lis.append(a[k])
   else:
     lis[bisect.bisect_left(lis,a[k])]=a[k]
   return lis
for i in range(n):
  #print(dp(i))
  print(len(dp(i)))

Submission status: Wrong Answer

Solution code:
import sys
from functools import lru_cache
from collections import defaultdict
from collections import deque
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n=read()
a=list(reads())
ls=[[] for i in range(n)]
count=[1]*n
for i in range(n-1):
  u,v=reads()
  u-=1
  v-=1
  ls[u].append(v)
nextls=[0]
while nextls:
  hoge2=nextls[:]
  nextls=[]
  #print(hoge2)
  for i in hoge2:
    hoge=ls[i]
    #print(hoge)
    nextls.extend(hoge)
    for ele in hoge:
        if a[ele]>a[i]:
          count[ele]=count[i]+1
        else:
          count[ele]=count[i]
for i in range(n):
  print(count[i])

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

# MOD = 10 ** 9 + 7
MOD = 998244353
# sys.setrecursionlimit(10**8)

n = int(input())
num = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for _ in range(n)]

for e in Edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

lis = [-1]*n
que = deque([(0, ())])
while que:
    node, arr = que.popleft()
    new_arr = list(arr)
    idx = bisect.bisect_left(arr, num[node])
    lis[node] = idx+1
    if idx < len(arr):
        new_arr[idx] = num[node]
    else:
        new_arr.append(num[node])
    # print(node, new_arr)

    for ne in graph[node]:
        if lis[ne] == -1:
            que.append((ne, tuple(new_arr)))


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

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

# MOD = 10 ** 9 + 7
MOD = 998244353
sys.setrecursionlimit(10**8)


def dfs(node, arr):
    # print(node, arr)
    new_arr = arr.copy()
    idx = bisect.bisect_left(arr, num[node])
    lis[node] = idx+1
    if idx < len(arr):
        new_arr[idx] = num[node]
    else:
        new_arr.append(num[node])
    # print(node, new_arr)

    for ne in graph[node]:
        if lis[ne] == -1:
            dfs(ne, new_arr)


n = int(input())
num = list(map(int, input().split()))
Edge = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for _ in range(n)]

for e in Edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

lis = [-1]*n
dfs(0, [])

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

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    visited = set()

    def dfs(v):
        visited.add(v)

        j = bisect.bisect_left(dp, A[v])
        before_val = dp[j]
        dp[j] = A[i]

        ans[v] = bisect.bisect_left(dp, inf)
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[j] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [0] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    visited = set()

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    def dfs(v):
        visited.add(v)
        changed_i, before_val = update_dp(v)
        ans[v] = changed_i + 1
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[changed_i] = before_val

    dfs(0)
    for a in ans:
        print(a)

main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    G = [[] for _ in range(N)]
    dp = [inf for _ in range(N)]
    ans = [1] * N
    for i in range(N-1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    visited = set()

    def update_dp(i):
        j = bisect.bisect_left(dp, A[i])
        before_val = dp[j]
        dp[j] = A[i]
        return j, before_val

    def dfs(v):
        visited.add(v)
        changed_i, before_val = update_dp(v)
        ans[v] = changed_i
        for next_v in G[v]:
            if next_v in visited:
                continue
            dfs(next_v)

        # restore dp
        dp[changed_i] = before_val
    dfs(0)
    for a in ans:
        print(a+1)

main()

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    a = LI()
    uv = [LI_() for _ in range(n-1)]

    e = collections.defaultdict(set)
    for u,v in uv:
        e[u].add(v)
        e[v].add(u)

    seg = Seg(n, 0, max)

    d = {}
    for i, c in enumerate(sorted(set(a))):
        d[c] = i
    z = [d[c] for c in a]

    rr = [0] * n
    def f(i, p, cr):
        ai = z[i]
        b = seg.find(ai)
        t = seg.query(0, ai)
        if cr < t + 1:
            cr = t + 1
        rr[i] = cr
        seg.update(ai, cr)
        for c in e[i]:
            if c == p:
                continue
            f(c, i, cr)
        seg.update(ai, b)

    f(0, -1, 0)

    return JA(rr, "\n")

print(main())

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
mod2 = 998244353
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res

def main():
    n = I()
    a = LI()
    uv = [LI_() for _ in range(n-1)]

    e = collections.defaultdict(set)
    for u,v in uv:
        e[u].add(v)
        e[v].add(u)

    seg = Seg(n, 0, max)

    d = {}
    for i, c in enumerate(sorted(set(a))):
        d[c] = i
    z = [d[c] for c in a]

    rr = [0] * n
    def f(i, p):
        ai = z[i]
        t = seg.query(0, ai)
        rr[i] = t + 1
        seg.update(ai, t+1)
        for c in e[i]:
            if c == p:
                continue
            f(c, i)
        seg.update(ai, 0)

    f(0, -1)

    return JA(rr, "\n")

print(main())

Submission status: Wrong Answer

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
import os

import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
VU = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

dp = [INF] * N
ans = [0] * N
root = 0


def dfs(v, p):
    i = bisect.bisect_left(dp, A[v])
    prev = dp[i]
    dp[i] = A[v]
    ans[v] = i + 1
    for u in graph[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = prev


dfs(root, None)
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect

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

res = [ [] for _ in range(N+1) ]
res[1] = [1]

def LIS(n, path):
  swapped = 0
  dp = []
  for i in path:
    if len(dp) == 0 or i > dp[-1]:
      dp.append(i)
    else:
      dp[bisect.bisect_left(dp, i)] = i
      swapped += 1
  res[n] = dp

def bfs():
  paths = [ [] for _ in range(N+1) ]
  q = [(1,[A[0]])]
  visited = [False] *(N+1)

  while q:
    node, path = q.pop(0)
    if node!=1 and path:
      LIS(node, path)
    visited[node] = True

    for nei in adj[node]:
      if visited[nei]: continue
      q.append((nei,path+[A[nei-1]]))

bfs()
for r in res[1:]:
  print(len(r))

Submission status: Wrong Answer

Solution code:
from numba import jit, njit, i8
from numba import jitclass, deferred_type
import numpy as np

T = i8
@njit(T(T, T))
def func(l, r):
  return max(l, r)

@jitclass([('seg', T[:]), ('I', T), ('size', i8)])
class SegmentTree:
  def __init__(self, N, I):
    self.I = I
    self.size = np.int64(1)
    while self.size < N:
      self.size *= 2
    self.seg = np.full(self.size * 2, I, dtype=T)

  def assign(self, k, x):
    self.seg[k + self.size] = x

  def build(self):
    for i in range(self.size - 1, 0, -1):
      self.seg[i] = func(self.seg[2 * i], self.seg[2 * i + 1])

  def update(self, k, x):
    k += self.size
    self.seg[k] = x
    while k > 1:
      k >>= 1
      self.seg[k] = func(self.seg[2 * k], self.seg[2 * k + 1])

  def query(self, a, b):
    L = self.I
    R = self.I
    a += self.size
    b += self.size
    while a < b:
      if a & 1:
        L = func(L, self.seg[a])
        a += 1
      if b & 1:
        b -= 1
        R = func(self.seg[b], R)
      a >>= 1
      b >>= 1
    return func(L, R)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000)

N = int(readline())
A = list(map(int,readline().split()))
UV = map(int, read().split())
g = [[] for _ in range(N)]
for u,v in zip(UV,UV):
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

inf = 1001001001
A.append(inf)
A.append(-inf)

X = np.sort(A)
X = np.unique(X)

seg = SegmentTree(len(X), 0)
ans = [0] * N

def dfs(i, p):
  idx = np.searchsorted(X, A[i])
  # idx未満で最大
  ans[i] = seg.query(0, idx) + 1
  old = seg.query(idx, idx+1)
  seg.update(idx, ans[i])
  for c in g[i]:
    if c == p: continue
    dfs(c, i)
  seg.update(idx, old)

dfs(0, -1)

for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
from numba import jit, njit, i8
from numba import jitclass, deferred_type
import numpy as np

T = i8
@njit(T(T, T))
def func(l, r):
  return max(l, r)

@jitclass([('seg', T[:]), ('I', T), ('size', i8)])
class SegmentTree:
  def __init__(self, N, I):
    self.I = I
    self.size = np.int64(1)
    while self.size < N:
      self.size *= 2
    self.seg = np.full(self.size * 2, I, dtype=T)

  def assign(self, k, x):
    self.seg[k + self.size] = x

  def build(self):
    for i in range(self.size - 1, 0, -1):
      self.seg[i] = func(self.seg[2 * i], self.seg[2 * i + 1])

  def update(self, k, x):
    k += self.size
    self.seg[k] = x
    while k > 1:
      k >>= 1
      self.seg[k] = func(self.seg[2 * k], self.seg[2 * k + 1])

  def query(self, a, b):
    L = self.I
    R = self.I
    a += self.size
    b += self.size
    while a < b:
      if a & 1:
        L = func(L, self.seg[a])
        a += 1
      if b & 1:
        b -= 1
        R = func(self.seg[b], R)
      a >>= 1
      b >>= 1
    return func(L, R)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000)

N = int(readline())
A = list(map(int,readline().split()))
UV = map(int, read().split())
g = [[] for _ in range(N)]
for u,v in zip(UV,UV):
  u -= 1
  v -= 1
  g[u].append(v)
  g[v].append(u)

inf = 1001001001
A.append(inf)
A.append(-inf)

X = np.sort(A)
X = np.unique(X)
print(X)

seg = SegmentTree(len(X), 0)

ans = [0] * N


def dfs(i, p):
  idx = np.searchsorted(X, A[i])
  ans[i] = seg.query(0, idx) + 1
  old = seg.query(idx, idx+1)
  seg.update(idx, ans[i])
  for c in g[i]:
    if c == p: continue
    dfs(c, i)
  seg.update(idx, old)

dfs(0, -1)

for i in ans:
  print(i)

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    maxlen = 0
    for (L, z) in table:
      if z <= x:
        maxlen = max(maxlen, L)
    table.append((maxlen+1, x))
  return max(L for (L, _) in table)
#print(longest_subsequence([1, 20, 15, 13, 7, 10, 10, 20, 11, 17, 4, 3, 9, 6, 2, 2, 20, 11]))
#sys.exit()
def BFS():
  node_sequences = [[] for _ in range(n)]
  visited = [False]*n
  queue_nodes = deque()
  queue_nodes.append((0, []))
  while queue_nodes:
    (vertex, sequence) = queue_nodes.popleft()
    visited[vertex] = True
    node_sequences[vertex] = sequence + [a[vertex]]
    for node in adjacent[vertex]:
      if not visited[node]:
        queue_nodes.append((node, node_sequences[vertex]))
  return node_sequences
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
long_sequences = BFS()
[print(longest_subsequence(sequence)) for sequence in long_sequences]

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    if x >= table[-1][1]:
      table.append((table[-1][0]+1, x))
    else:
      maxlen = 0
      for (L, z) in table:
        if z <= x:
          maxlen = max(maxlen, L)
      table.append((maxlen+1, x))
  return max(L for (L, _) in table)
#print(longest_subsequence([20, 21, 21, 19, 19, 19, 19]))
#sys.exit()
def BFS():
  node_sequences = [[] for _ in range(n)]
  visited = [False]*n
  queue_nodes = deque()
  queue_nodes.append((0, []))
  while queue_nodes:
    (vertex, sequence) = queue_nodes.popleft()
    visited[vertex] = True
    node_sequences[vertex] = sequence + [a[vertex]]
    for node in adjacent[vertex]:
      if not visited[node]:
        queue_nodes.append((node, node_sequences[vertex]))
  return node_sequences
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
long_sequences = BFS()
[print(longest_subsequence(sequence)) for sequence in long_sequences]

Submission status: Wrong Answer

Solution code:
from collections import deque
def longest_subsequence(sequence):
  table = [(1, sequence[0])]
  for x in sequence[1:]:
    if x >= table[-1][1]:
      table.append((table[-1][0]+1, x))
    else:
      maxlen = float("-inf")
      for (L, z) in table:
        if z <= x:
          maxlen = max(maxlen, L)
      table.append((maxlen+1, x))
  return max(L for (L, _) in table)
def BFS():
  node_sequences = [[] for _ in range(n)]
  visited = [False]*n
  queue_nodes = deque()
  queue_nodes.append((0, []))
  while queue_nodes:
    (vertex, sequence) = queue_nodes.popleft()
    visited[vertex] = True
    node_sequences[vertex] = sequence + [a[vertex]]
    for node in adjacent[vertex]:
      if not visited[node]:
        queue_nodes.append((node, node_sequences[vertex]))
  return node_sequences
n = int(input())
a = list(map(int, input().split()))
adjacent = {i: [] for i in range(n)}
for _ in range(n-1):
  node1, node2 = map(int, input().split())
  node1 -= 1
  node2 -= 1
  adjacent[node1].append(node2)
  adjacent[node2].append(node1)
long_sequences = BFS()
[print(longest_subsequence(sequence)) for sequence in long_sequences]

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
#F

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
for _ in range(n-1):
    u, v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

dp = [inf]*n
ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(s, p, dp, num):
    for u in edges[s]:
        flag = False
        if u == p:
            continue
        r = br(dp, a[u])
        tmp = dp[r]
        if dp[r] == inf:
            num += 1
            flag = True
        ans[u] = num
        dp[r] = min(dp[r], a[u])
        dfs(u, s, dp, num)
        dp[r] = tmp
        if flag:
            num -= 1
    return
dfs(0, -1, dp, 1)

for i in ans:
    print(i)