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: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
n = ni()
A = lma()
tree = [[] for i in range(n)]
INF = 10**10
for i in range(n-1):
    u,v = ma();u-=1;v-=1
    tree[u].append(v)
    tree[v].append(u)
#print(tree)
def isok(num,val):##適宜変更
    return num<val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ
def solve():
    ans = [0]*n
    s = 0
    stack = collections.deque()
    visited=[False]*n
    visited[s]=True
    ls_p=[INF]
    stack.appendleft((s,0,ls_p))
    while stack:
        prev,right,ls_p = stack.popleft()
        #print(prev)
        ans[prev]= LIS_1(A[prev],ls_p,right)
        #print(prev,ls_p,tree[prev])
        for node in tree[prev]:
            if not visited[node]:
                if len(tree[prev])<=2 and prev!=s:
                    ls_n =ls_p
                else:
                    ls_n = ls_p.copy()
                ls_n.append(INF)
                visited[node]=True
                stack.appendleft((node,ans[prev],ls_n))
    return ans
def LIS_1(x,ls,right):##right ::これまでわかっている右端
    idx = bisect(ls,x)+1
    if idx+1>right:
        ret = idx+1
    else:
        ret=right
    ls[idx]=x
    #print(x,ls)
    return ret

ans = solve()
for a in ans :
    print(a)

Submission status: Time Limit Exceeded

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.copy()))
                dp[bis]=updatetask
 
    print(*dist[1:], sep="\n")
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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()
        graph2=[]
        for i in graph[v]:
            if dist[i] == -1:
                graph2.append(i)
        for index, i in enumerate(graph2,1):
            if index==len(graph2):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                ndp=dp.copy()
                if dp[-1] < A[i]:
                    ndp.append(A[i])
                else:
                    bis = bisect.bisect_left(ndp, A[i])
                    ndp[bis] = A[i]
                dist[i] = len(ndp)-1
                d.append((i, ndp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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 index, i in enumerate(graph[v],1):
            if dist[i] != -1:
                continue
            if index==len(graph[v]):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                ndp=dp.copy()
                if dp[-1] < A[i]:
                    ndp.append(A[i])
                else:
                    bis = bisect.bisect_left(ndp, A[i])
                    ndp[bis] = A[i]
                dist[i] = len(ndp)-1
                d.append((i, ndp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

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 index, i in enumerate(graph[v],1):
            if dist[i] != -1:
                continue
            if index==len(graph[v]):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                newdp = update(dp, A[i])
                dist[i] = len(newdp)-1
                d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

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
            newdp = update(dp, A[i])
            dist[i] = len(newdp)-1
            d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()


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


def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp


while d:
    v, dp = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        newdp = update(dp, A[i])
        dist[i] = len(newdp)-1
        d.append((i, newdp))

ans = dist[1:]
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect

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

def update(dp,AA):
    ndp=dp.copy()
    if ndp[-1]<AA:
        ndp.append(AA)
    else:
        bis=bisect.bisect_left(ndp, AA)
        ndp[bis]=AA
    return ndp

while d:
    v,dp = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        newdp=update(dp,A[i])
        dist[i] = len(newdp)-1
        d.append((i,newdp))

ans = dist[1:]
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
import sys
sys.setrecursionlimit(10**6)
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=[0]*n
dp=[float("inf")]*n
def f(c,d,dp):
    h=bl(dp,a[c])
    q=dp[::]
    q[h]=a[c]
    b[c]=bl(q,float("INF"))
    for i in t[c]:
        if i!=d:f(i,c,q)
f(0,-1,dp)
for i in b:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
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=bl(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: Time Limit Exceeded

Solution code:
from bisect import bisect_left as bl
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]]+[2**64]*(n-1),1]]
while q:
    c,d,e=q.pop(0)
    for i in t[c]:
        if b[i]==0:
            s=d[::]
            g=e
            h=bl(d,a[i])
            s[h]=a[i]
            if e<=h:
                g+=1
            b[i]=g
            q.append([i,s,g])
for i in range(n):
    print(b[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u][v] = 1
  uv[v][u] = 1


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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u][v] = 1
  uv[v][u] = 1

def main():
  ans = [0] * n
  que = deque([0])
  ans[0] = 1
  while que:
    x = que.popleft()
    ansx = ans[x]
    ax = a[x]
    for i in range(n):
      ansi = ans[i]
      ai = a[i]
      if uv[x][i] == 1 and ansi == 0:
        if ai > ax:
          ans[i] = ansx + 1
        else:
          ans[i] = ansx
        que.append(i)
  return ans

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u][v] = 1
  uv[v][u] = 1

ans = [0] * n
que = deque([0])
ans[0] = 1
while que:
  x = que.popleft()
  ansx = ans[x]
  ax = a[x]
  for i in range(n):
    ansi = ans[i]
    ai = a[i]
    if uv[x][i] == 1 and ansi == 0:
      ans[i] = ansx
      if ai > ax:ans[i] += 1
      que.append(i)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

for i in range(n-1):
  u,v = list(map(int, input().split()))
  u -= 1
  v -= 1
  uv[u][v] = 1
  uv[v][u] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

for i in range(n-1):
  u,v = list(map(int, input().split()))
  uv[u-1][v-1] = 1
  uv[v-1][u-1] = 1

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n  = int(input())
a = list(map(int, input().split()))
uv = [[0]*n for _ in range(n)]

for i in range(n-1):
  u,v = list(map(int, input().split()))
  uv[u-1][v-1] = 1
  uv[v-1][u-1] = 1

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

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

Submission status: Time Limit Exceeded

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**12
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):
    #ddprint(f"dfs {u=} {j=}")
    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]
        #ddprint(f"dfs {u=} {j=} {x=} {tmp=} av {a[v]} {dp=}")
        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[0] = a[1]
dfs(1,1,dp)
for i in range(1,n+1):
    print(ans[i])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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
x,y,z=0,0,0
def dfs(DP,now,prev,lis):
  x=bisect_left(DP,A[now])
  z=lis
  lis=max(lis,x)
  y=DP[x]
  DP[x]=A[now]
  P[now]=lis
  for i in range(len(G[now])):
    if G[now][i]!=prev:
      dfs(DP,G[now][i],now,lis)
  DP[x]=y
  lis=z

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

Submission status: Time Limit Exceeded

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,lis):
  x=bisect_left(DP,A[now])
  z=lis
  lis=max(lis,x)
  y=DP[x]
  DP[x]=A[now]
  P[now]=lis
  for i in range(len(G[now])):
    if G[now][i]!=prev:
      dfs(DP,G[now][i],now,lis)
  DP[x]=y
  lis=z

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
a = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
L = [a[0]]
que.append((0,1,L))
chk = [False]*n
chk[0] = True
cnt = 1
ans = [1]*n
while que:
  now,m,L = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      ind = bisect_left(L,a[i])
      if m == ind:
        newm = m+1
        newL = L+[a[i]]
      else:
        newm = m
        newL = L[:ind]+[a[i]]+L[ind+1:]
      ans[i] = newm
      chk[i] = True
      cnt += 1
      que.append((i,newm,newL))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import deque
from bisect import bisect_left

n = int(readline())
a = list(map(int,readline().split()))
g = [[] * n for i in range(n)]
for i in range(n-1):
    u, v = map(int, readline().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
    
que = deque()
L = [a[0]]
que.append((0,1,L))
chk = [False]*n
chk[0] = True
cnt = 1
ans = [1]*n
while que:
  now,m,L = que.popleft()
  if cnt == n:
    break
  for i in g[now]:
    if not chk[i]:
      newL = L.copy()
      ind = bisect_left(L,a[i])
      if m == ind:
        newm = m+1
        newL.append(a[i])
      else:
        newm = m
        newL[ind] = a[i]
      ans[i] = newm
      chk[i] = True
      cnt += 1
      que.append((i,newm,newL))

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

Submission status: Time Limit Exceeded

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

input = sys.stdin.readline

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

tree = [[] for _ in range(n)]
for _ 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
visited = [0] * n
visited[0] = 1


def dfs(i, l):
    s = a[i]
    if len(l) == 0 or s > l[-1]:
        l.append(s)
    else:
        l[bisect.bisect_left(l, s)] = s
    ans[i] = len(l)

    for ni in tree[i]:
        if not visited[ni]:
            visited[ni] = 1
            dfs(ni, l[:])


dfs(0, [])

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import deque
import copy

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

edge_array = deque([(1, [0])])
use_array[0] = 1

while(len(edge_array)):
    edge, arr = edge_array.popleft()
    # print(edge, arr, ans_array)

    insert = bisect.bisect_left(arr, a_array[edge - 1])
    if insert == len(arr):
        arr.append(a_array[edge - 1])
    else:
        arr[insert] = a_array[edge - 1]
    ans_array[edge - 1] = len(arr) - 1
    for next_edge in node_dic[edge]:
        if use_array[next_edge - 1] == -1:
            use_array[next_edge - 1] = 1
            arr_next = copy.deepcopy(arr)
            edge_array.append((next_edge, arr_next))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from scipy.sparse import lil_matrix
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
def get_path(s,g,p):
    return get_path_row(s,g,p[s])
def get_path_row(s,g,pr):
    path=[]
    i=g
    while i!=s and i>=0:
        path.append(i)
        i=pr[i]
    if i<0:return[]
    path.append(i)
    return path[::-1]
def lis(a):
    dp,res=[1]*len(a),0
    for i in range(len(a)):
        for j in range(i):
            if a[j]<a[i]:dp[i]=dp[j]+1 if dp[i]<dp[j]+1 else dp[i]
        res=dp[i] if res<dp[i] else res
    return res
def main():
    N=int(sys.stdin.readline().strip())
    a=list(map(int,sys.stdin.readline().split()))
    es=lil_matrix((N,N))
    for _ in [0]*(N-1):
        u,v=tuple(map(int,sys.stdin.readline().split()))
        u,v=u-1,v-1
        es[u,v],es[v,u]=1,1
    es=es.tocsr()
    cs,ss=dijkstra(es,indices=0,return_predecessors=True,unweighted=True)
    for i in range(N):
        j,p=i,[]
        while True:
            p=[a[j]]+p
            if ss[j]<0:break
            j=ss[j]
        print(lis(p))
if __name__=='__main__':main()

Submission status: Time Limit Exceeded

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):
    dp,res=[1]*len(a),0
    for i in range(len(a)):
        for j in range(i):
            if a[j]<a[i]:dp[i]=dp[j]+1 if dp[i]<dp[j]+1 else dp[i]
        res=dp[i] if res<dp[i] else res
    return res
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,1))
        es[v].append((u,1))
    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: Time Limit Exceeded

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)
        changed_i, before_val = update_dp(v)
        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[changed_i] = before_val

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

main()

Submission status: Time Limit Exceeded

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
        if b < t + 1:
            seg.update(ai, t + 1)
        for c in e[i]:
            if c == p:
                continue
            f(c, i, cr)
        if b < t + 1:
            seg.update(ai, b)

    f(0, -1, 0)

    return JA(rr, "\n")

print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from bisect import bisect_left
 
# N = int(input())
# A = list(map(int,input().split()))
N = int(sys.stdin.buffer.readline())
A =  [int(x) for x in sys.stdin.buffer.readline().split()]
adj = [ [] for _ in range(N+1) ]
for _ in range(N-1):
  # a,b = map(int,input().split())
  a,b =  [int(x) for x in sys.stdin.buffer.readline().split()]
  a -= 1
  b -= 1
  adj[a].append(b)
  adj[b].append(a)
 
INF = 10**15
# dp = [ INF for _ in range(2*10**5+1)]
dp = [INF]*(2*10**5+1)
dp[0] = -INF
ans = [None]*(N)
 
def dfs(v, p=-1):
  i = bisect_left(dp, A[v])
  old = dp[i]
  dp[i] = A[v]
  ans[v] = i
  if p!=-1: ans[v] = max(ans[v], ans[p])
 
  for u in adj[v]:
    if u == p: continue
    dfs(u, v)
 
  dp[i] = old
 
dfs(0)
for i in range(N):
  print(ans[i])