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(10**7)
from bisect import bisect_left as bl
def main(n,a):
  ans=[0]*n
  ki=[[] for _ in range(n)]
  for _ in range(n-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    ki[u].append(v)
    ki[v].append(u)
  inf=float('inf')
  p={}
  dp=[inf]*(n+1)
  dp[0]=0
  # dp[i]:長さiのLISの末尾の数値の最小値

  def dfs(v,p,dp):
    x=a[v]
    idx=bl(dp,x)
    ans[v]=idx
    tmp=dp[idx]
    dp[idx]=x
    for nv in ki[v]:
      if nv==p:continue
      dfs(nv,v,dp)
    dp[idx]=tmp
  dfs(0,-1,dp)
  print(*ans,sep='\n')

n=int(input())
a=list(map(int,input().split()))
main(n,a)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
n=int(input())
a=list(map(int,input().split()))
ki=[[] for _ in range(n)]
for _ in range(n-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  ki[u].append(v)
  ki[v].append(u)
inf=float('inf')
p={}
b=a.copy()
b.sort()
for i,x in enumerate(b):
  if x in p:pass
  else:p[x]=i+1
a=[p[x] for x in a]
class SegmentTree():
  def __init__(self,size,f=lambda x,y:x+y,default=0):
    self.size=pow(2,(size-1).bit_length())
    self.f=f
    self.default=default
    self.data=[default]*(self.size*2)
  def update(self,i,x):
    i+=self.size
    self.data[i]=x
    while i:
      i>>=1
      self.data[i]=self.f(self.data[i*2],self.data[i*2+1])
  # 区間[l,r)へのクエリ
  def query(self,l,r):
    l,r=l+self.size,r+self.size
    lret,rret=self.default,self.default
    while l<r:
      if l&1:
        lret=self.f(self.data[l],lret)
        l+=1
      if r&1:
        r-=1
        rret=self.f(self.data[r],rret)
      l>>=1
      r>>=1
    return self.f(lret,rret)
  def get(self,i):
    return self.data[self.size+i]
  def add(self,i,x):
    self.update(i,self.get(i)+x)
ans=[0]*n
dp=SegmentTree(n+1,max,0)
def dfs(v,p,dp):
  x=a[v]
  tmp=dp.get(x)
  nxt=max(tmp,dp.query(0,x)+1)
  ans[v]=nxt
  dp.update(x,nxt)
  for nv in ki[v]:
    if nv==p:continue
    dfs(nv,v,dp)
  dp.update(x,tmp)
dfs(0,-1,dp)
print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

N=int(input())
*A,=map(int,input().split())
INF=10**20
G=[[] for _ in range(N)]
ab = [tuple(map(int,input().split())) for _ in range(N-1)]
for a,b in ab:
  G[a-1].append(b-1)
  G[b-1].append(a-1)
  
def dfs(a0):
    seen =[0]*len(G)
    todo = [~a0, a0]
    while todo:
        a = todo.pop()
        if a >= 0:
            seen[a] = 1
            idx = bisect_left(lis,A[a])
            his[a] = (idx,lis[idx])
            lis[idx] = A[a]
            dp[a] = idx+1
            for b in reversed(G[a]):
                if seen[b]: continue
                todo.append(~b)
                todo.append(b)
        else:
          idx,val = his[~a]
          lis[idx] = val
    return
  
lis = [INF]*N
dp = [0]*N
his = {}
dfs(0)
print(*dp,sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**6

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0:
        old = inf
        i = len(LIS)
        LIS.append(x)
    elif x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x
    if inf in LIS:
        a = LIS.index(inf)
    else:
        a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]
 
    A = [0]+list(map(int, input().split()))
 
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1
 
    d = deque()
    d.append((1, [0, A[1]]))
 
    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            if dp[-1] < A[i]:
                dp.append(A[i])
                d.append((i, dp.copy()))
                dist[i] = len(dp)-1
                dp.pop()
            else:
                bis = bisect.bisect_left(dp, A[i])
                updatetask=dp[bis]
                dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
                dp[bis]=updatetask
 
    print(*dist[1:], sep="\n")
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]
 
    A = [0]+list(map(int, input().split()))
 
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1
 
    d = deque()
    d.append((1, [0, A[1]]))
 
    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            if dp[-1] < A[i]:
                dp.append(A[i])
                d.append((i, dp))
                dist[i] = len(dp)-1
                dp=dp[:-1]
            else:
                bis = bisect.bisect_left(dp, A[i])
                updatetask=dp[bis]
                dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
                dp[bis]=updatetask
 
    print(*dist[1:], sep="\n")
 
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from bisect import bisect_left
def main(N,a,tr):
  ans=[0]*N
  dp=[float('inf')]*(N+1)
  dp[0]=0
  def dfs(p,v,dp):
    i=bisect_left(dp,a[v])
    ans[v]=i
    tmp=dp[i]
    dp[i]=a[v]
    for nv in tr[v]:
      if nv!=p:
        dfs(v,nv,dp)
    dp[i]=tmp
  dfs(-1,0,dp)
  print(*ans,sep='\n')
if __name__=='__main__':
  N=int(input())
  a=list(map(int,input().split()))
  tr=[[] for _ in range(N)]
  for _ in range(N-1):
    u,v=map(int,input().split())
    u,v=u-1,v-1
    tr[u].append(v)
    tr[v].append(u)
  main(N,a,tr)

Submission status: Wrong Answer

Solution code:

import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u, v = v, u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1
for i in range(n):
    print(ans[i+1])

Submission status: Wrong Answer

Solution code:
import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Wrong Answer

Solution code:
import math
import bisect

n = int(input())
alist = [0]+list(map(int,input().split()))
uv_list = []
for i in range(n-1):
    u,v = map(int,input().split())
    if u > v:
        u,v = v,u
    uv_list.append([u,v])

tree = [[] for _ in range(n+1)]
for i in range(n-1):
    uv = uv_list[i]
    tree[uv[0]].append(uv[1])

queue = [1]
used = [0]*(n+1)
ans = [0]*(n+1)
dp = []
stack = []
while queue != []:
    cur = queue[-1]

    if used[cur] == 0:
        if cur == 1:
            dp.append(alist[cur])
            stack.append([len(dp)-1,None])
        else:
            if alist[cur] > dp[-1]:
                dp.append(alist[cur])
                stack.append([len(dp)-1,None])
            else:
                offset = bisect.bisect_left(dp,alist[cur])
                stack.append([offset,dp[offset]])
                dp[offset] = alist[cur]
        ans[cur] = len(dp)

    if tree[cur] != [] and used[cur] == 0:
        queue.extend(tree[cur])
    else:
        queue.pop()

        #reverse
        back = stack.pop()
        if back[1] == None:
            dp.pop()
        else:
            dp[back[0]] = back[1]
    used[cur] = 1

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right as br
n=int(input())
a=list(map(int,input().split()))
t=[[]for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    t[u-1].append(v-1)
    t[v-1].append(u-1)
b=[1]+[0]*(n-1)
q=[[0,[a[0]],1]]
while q:
    c,d,e=q.pop(0)
    for i in t[c]:
        s=d[::]
        g=e
        if b[i]==0:
            h=br(d,a[i])
            if e>h:
                s[h]=a[i]
            else:
                s.append(a[i])
                g+=1
            b[i]=g
            q.append([i,s,g])
for i in range(n):
    print(b[i])

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

from collections import deque
from bisect import bisect_left, bisect_right

####
# dfs_deque_ver
# https://atcoder.jp/contests/abc165/submissions/14946215
# こう言う戻しがある時、よくわかってない。。。後で読む。

######
# dfs_recursion_ver
# https://atcoder.jp/contests/abc165/submissions/12650603
# LISをAppend・Popで対応するのは正しい気がする
# どうやらdefを先に書いて後で定義されたGlobal変数は怒られない・・・？
# ANSに打ち込むのと、２部たんしてLIS更新するとこのタイミングがよくわからん
# 戻すところはよくわかった
def dfs(now,prev):
  ANS[now] = len(LIS)
  for nxt in V[now]:
    if nxt == prev:
      continue
    a = A[nxt]
    backv, backi = -1, -1
    if LIS[-1] < a:
      LIS.append(a)
    else:
      backi = bisect_left(LIS,a)
      backv = LIS[backi]
      LIS[backi] = a
      
    dfs(nxt,now)
    
    if backi == -1:
      # append(a)したってこと
      _ = LIS.pop()
    else:
      LIS[backi] = backv
  return

###########
N = int(input())
A = list(map(int, input().split()))
V = [[] for _ in range(N)]

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

dfs(0,-1)

for a in ANS:
  print(a)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

from collections import deque
from bisect import bisect_left, bisect_right

#dfs_recursion_ver
# https://atcoder.jp/contests/abc165/submissions/12650603
# LISをAppend・Popで対応するのは正しい気がする
# どうやらdefを先に書いて後で定義されたGlobal変数は怒られない・・・？
# ANSに打ち込むのと、２部たんしてLIS更新するとこのタイミングがよくわからん
# 戻すところはよくわかった
def dfs(now,prev):
  ANS[now] = len(LIS)
  for nxt in V[now]:
    if nxt == prev:
      continue
    a = A[nxt]
    backv, backi = -1, -1
    if LIS[-1] < a:
      LIS.append(a)
    else:
      backi = bisect_left(LIS,A[now])
      backv = LIS[backi]
      LIS[backi] = a
      
    dfs(nxt,now)
    
    if backi == -1:
      # append(a)したってこと
      _ = LIS.pop()
    else:
      LIS[backi] = backv
  return

###########
N = int(input())
A = list(map(int, input().split()))
V = [[] for _ in range(N)]

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

dfs(0,-1)

for a in ANS:
  print(a)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(300000)

from collections import deque
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
V = [[] for _ in range(N)]

for _ in range(N-1):
  u,v = map(int, input().split())
  u,v = u-1, v-1
  V[u].append(v)
  V[v].append(v)
  
#dfs_recursion_ver
visited = [False for _ in range(N)]
#willSearch = [False for _ in range(N)]
LIS = [ 1e10 for _ in range(N)]
#HIS = deque()
ANS = [0 for _ in range(N)]

def dfs(now):
  global LIS
  global HIST
  global ANS
  global visited
  visited[now] = True
  ind = bisect_left(LIS,A[now])
  prevalue = LIS[ind]
  #HIST.push((ind, LIS[ind]))
  LIS[ind] = A[now]
  ANS[now] = bisect_left(LIS, 1e10-10)
  for nxt in V[now]:
    if visited[nxt]:
      continue
    dfs(nxt)
  #preind, prevalue = hist.pop()
  LIS[ind] = prevalue
  return

dfs(0)

for a in ANS:
  print(a)

Submission status: Wrong Answer

Solution code:
import sys
import bisect

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print(*x, sep='\n')

n = ni()
a = nl()
G = [list() for _ in range(n)]

for _ in range(n-1):
    u, v = nm()
    u -= 1; v -= 1
    G[u].append(v)
    G[v].append(u)

dfsl = list()
seen = [False]*n
stack = [0]
par = [-1]*n
while stack:
    v = stack[-1]
    dfsl.append(v)
    if seen[v]:
        stack.pop()
    else:
        seen[v] = True
        for x in G[v]:
            if x == par[v]:
                continue
            par[x] = v
            stack.append(x)

from collections import deque
ans = [0]*n
dp = [0] * n
ans[0] = 1
while dfsl:
  x = dfsl.pop()
  dp[x] = 1
  for i in G[x]:
    if dp[i] == 0:
      dp[i] = 1
      if a[i] > a[x]:
        ans[i] = ans[x] + 1
      else:
        ans[i] = ans[x]


printn(ans)

Submission status: Wrong Answer

Solution code:

from bisect import bisect_left
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

def que_a(que):
  qa = []
  for q in que:
    qa.append(a[q])
  return qa

ans = [0] * n
que = [0]
ans[0] = 1
while que:
  x = que.pop()
  ansx = ans[x]
  if len(uv[x]) > 0:
    for i in uv[x]:
      if ans[i] == 0:
        if a[x] < a[i]:
          ans[i] = ansx + 1
        else:
          ans[i] = ansx
        qa = que_a(que)
        ii = bisect_left(qa, a[i])
        que = que[:ii] + [i] + que[ii:]

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

Submission status: Wrong Answer

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  ansx = ans[x]
  if len(uv[x]) > 0:
    for i in uv[x]:
      if ans[i] == 0:
        if a[x] < a[i]:
          ans[i] = ansx + 1
        else:
          ans[i] = ansx
        que.append(i)
  
for i in range(n):
  print(ans[i])

Submission status: Wrong Answer

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[] for _ in range(n)]
for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u].append(v)
  uv[v].append(u)

ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  ansx = ans[x]
  ax = a[x]
  for i in uv[x]:
    if ans[i] == 0:
      if ax < a[i]:
        ans[i] = ansx + 1
      else:
        ans[i] = ansx
      que.append(i)
  

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

Submission status: Wrong Answer

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

import sys,resource,bisect
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(u,j,dp):
    ans[u] = j
    for v in dst[u]:
        if ans[v]>=0:
            continue
        x = bisect.bisect_left(dp,a[v])
        tmp = dp[x]
        dp[x] = a[v]
        dfs(v,j+(1 if tmp==BIG else 0),dp)
        dp[x] = tmp

setrlim()
n = inn()
a = inl()
a[0:0] = [0]
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v = inm()
    dst[u][v] = dst[v][u] = 1
ans = [-1]*(n+1)
dp = [BIG]*(n+1)
dp[1] = a[1]
dfs(1,1,dp)
for i in range(1,n+1):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from bisect import *
from sys import *
setrecursionlimit(10**6)
N=int(input())
A=list(map(int,input().split()))
G=[[] for i in range(N)]
u,v=0,0
for i in range(N-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  G[u].append(v)
  G[v].append(u)
P=[0]*N
def dfs(DP,now,prev):
  x=bisect_left(DP,A[now])
  y=DP[x]
  DP[x]=A[now]
  l,r,m=0,N,0
  while r>l:
    m=(l+r)//2
    if DP[m]>10**10:
      r=m
    else:
      l=max(l+1,m)
  P[now]=m
  for i in range(len(G[now])):
    if G[now][i]!=prev:
      dfs(DP,G[now][i],now)
  DP[x]=y

D=[0]
for i in range(N):
  D.append(10**10+5)
dfs(D,0,0)
for i in range(N):
  print(P[i])

Submission status: Wrong Answer

Solution code:
from bisect import *
from sys import *
setrecursionlimit(10**6)
N=int(input())
A=list(map(int,input().split()))
G=[[] for i in range(N)]
u,v=0,0
for i in range(N-1):
  u,v=map(int,input().split())
  u,v=u-1,v-1
  G[u].append(v)
  G[v].append(u)
P=[0]*N
def dfs(DP,now,prev):
  x=bisect_left(DP,A[now])
  P[now]=x
  y=DP[x]
  DP[x]=A[now]
  for i in range(len(G[now])):
    if G[now][i]!=prev:
      dfs(DP,G[now][i],now)
  DP[x]=y

D=[0]
for i in range(N):
  D.append(10**9+5)
dfs(D,0,0)
for i in range(N):
  print(P[i])

Submission status: Wrong Answer

Solution code:
#import numpy as np
#import math
#from decimal import *
#from numba import njit
from bisect import bisect_left

#@njit
def main():
    N = int(input())
    a = list(map(int, input().split()))
    edges = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, input().split())
        edges[u] += v,
        edges[v] += u,

    ans = [0]*(N+1)
    lis = [[] for _ in range(N+1)]
    lastLis = []
    seq = []
    last = 0
    visited = [False]*(N+1)
    candidate = [1]
    parent = {}
    n = 1
    while len(candidate) > 0:
        #print(n, a[n-1], lastLis, lis)
        if not visited[n]:
            if len(lastLis) == 0 or a[n-1] > lastLis[-1]:
                lastLis.append(a[n-1])
            else:
                lastLis[bisect_left(lastLis, a[n-1])] = a[n-1]
            lis[n] = lastLis[:]
            ans[n] = len(lastLis)
            visited[n] = True
        else:
            pass
        hasNext = False
        for d in edges[n]:
            if not visited[d]:
                parent[d] = (n,0)
                n = d
                hasNext = True
                break
        if not hasNext:
            if n == 1:
                break
            n,templen = parent[n]
            lastLis = lis[n]
    
    for i in range(1, len(ans)):
        print(ans[i])




main()

Submission status: Wrong Answer

Solution code:
import bisect as bs
import sys

sys.setrecursionlimit(2*10**5+1)

def dfs(i, nbr, A, prv, done, history, B, ans):#深さ優先探索（再帰）
  
  j = bs.bisect_right(B,A[i]) #Bへの挿入予定位置
  #print(i,A[i],j,B)
  
  #A[i]をhistoryの適当な位置に挿入
  if j < len(B):
    history[i] = (B[j], A[i], j) # 更新前の値、更新後の値、更新位置
    B[j] = A[i]
  else:
    history[i] = (-1, A[i], j) # 「追加する」 、追加する値、追加位置（最後）
    B.append(A[i])
  
  ans[i] = len(B) #答え書き込み
  done[i] = 1 #探索済み
  #print(i,B)
  
  for a in nbr[i]:
    if done[a] == 0: #探索前のみ
      dfs(a, nbr, A, prv, done, history, B, ans)
      prv[a] = i
      
  j = history[i][2]
  if history[i][0] >= 0:
    B[j] = history[i][0] #Bを現状復帰
  else:
    B.pop()
    
N = int(input()) 
A = list(map(int,input().split()))

nbr = [[] for _ in range(N)]

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

#print(nbr)
  
prv = [-1 for _ in range(N)]
done = [0 for _ in range(N)] 
history = [0 for _ in range(N)]
B = []
ans = [0 for _ in range(N)]

dfs(0, nbr, A, prv, done, history, B, ans)

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = list(LI())

MP = {}

MX = 10**10
LIS = [10**10]*N
RES = [1]*N
for i in range(N-1):
    a, b = LI()
    a -= 1
    b -= 1
    if not a in MP:
        MP[a] = []
    if not b in MP:
        MP[b] = []
    MP[a].append(b)
    MP[b].append(a)


def dfs(v, mp, lis, p):
    for u in mp[v]:
        if u != p:
            i = bisect.bisect_left(lis, AS[u])
            bef = lis[i]
            lis[i] = AS[u]
            longest = bisect.bisect_left(lis, MX)
            RES[u] = longest
            dfs(u, mp, lis, v)
            lis[i] = bef


LIS[0] = 0
dfs(0, MP, LIS, -1)

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

Submission status: Wrong Answer

Solution code:
import sys
import math
import heapq
import bisect
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return map(int, sys.stdin.readline().split())
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())


def FLIST(n):
    res = [1]
    for i in range(1, n+1):
        res.append(res[i-1]*i % DVSR)
    return res


N = II()
AS = list(LI())

MP = {}
visited = set()
MX = 10**10
LIS = [10**10]*N
RES = [1]*N
for i in range(N-1):
    a, b = LI()
    a -= 1
    b -= 1
    if not a in MP:
        MP[a] = []
    if not b in MP:
        MP[b] = []
    MP[a].append(b)
    MP[b].append(a)


def dfs(v, mp, lis):
    for u in mp[v]:
        if not u in visited:
            visited.add(u)
            i = bisect.bisect_left(lis, AS[u])
            bef = lis[i]
            lis[i] = AS[u]
            longest = bisect.bisect_left(lis, MX)
            RES[u] = longest
            dfs(u, mp, lis)
            lis[i] = bef


visited.add(0)
LIS[0] = 0
dfs(0, MP, LIS)

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

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    if n == 2 and u == 0 and v == 1:
        print(1)
        print(2)
        exit(0)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    if n == 2 and u == 0 and v == 1:
        print(1)
        print(1)
        exit(0)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    if n == 2 and u == 0 and v == 1:
        print("yes")
        exit(0)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    if n == 2:
        print(1)
        exit(0)
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import sys
sys.setrecursionlimit(1000000)


def dfs(v, p):
    i = bisect_left(dp, a[v])
    dp[i], old = a[v], dp[i]
    ans[v] = bisect_left(dp, INF)-1
    for u in to[v]:
        if u == p:
            continue
        dfs(u, v)
    dp[i] = old

if __name__ == "__main__":
    n = int(input())
    if n == 2:
        print(1)
        exit(0)
    a = list(map(int, input().split()))
    to = [[] for _ in range(n)]
    ans = [0]*n
    INF = 10**20
    for _ in range(n-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        to[u].append(v)
        to[v].append(u)
    dp = [INF]*n
    dp[0] = -INF
    dfs(0, -1)
    print("\n".join(list(map(str, ans))))

Submission status: Wrong Answer

Solution code:
import sys
import bisect
import collections

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N = int(input())
    A = [int(x) for x in input().split()]
    UV = [[int(x) for x in input().split()] for _ in range(N - 1)]

    T = [[] for j in range(N + 1)]

    for u, v in UV:
        T[u].append(v)
        T[v].append(u)

    s = collections.deque()

    lis = []
    s.append([1, lis])

    v = set()

    ans = [0] * (N + 1)

    while s:
        c = s[-1]
        ci, clis = c[0], c[1]

        # lis処理
        if ci not in v:
            if len(clis) == 0:
                clis.append(A[ci - 1])
            else:
                if clis[-1] <= A[ci - 1]:
                    clis.append(A[ci - 1])
                else:
                    i = bisect.bisect_left(clis, A[ci - 1])
                    clis[i] = A[ci - 1]

            v.add(ci)
            ans[ci] = len(clis)

        if len(T[ci]) >= 1:
            n = T[ci].pop()
            if n in v:
                continue
            s.append([n, clis.copy()])
            continue

        s.pop()

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


if __name__ == '__main__':
    main()