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: Accepted

Solution code:
#F
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
a = list(map(int, input().split()))
lists=[[] for i in range(N)]
for i in range(N-1):
    u, v = map(int, input().split())
    lists[u-1].append(v-1)
    lists[v-1].append(u-1)

def search(v,LIS):
    if len(lists[v])==0:
        return
    for u in lists[v]:
        if check[u] == False:
            check[u] = True
            if a[u] > LIS[-1]:
                LIS.append(a[u])
                ans[u] = len(LIS)
                search(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,a[u])
                stack = LIS[ind]
                LIS[ind]=a[u]
                ans[u] = len(LIS)
                search(u,LIS)
                LIS[ind]=stack
    return

ans = [0]*N
check = [False]*N
check[0]=True
LIS = [a[0]]
ans[0]=1
search(0,LIS)
print(*ans, sep="\n")

Submission status: Accepted

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

from collections import deque

vi = 0  #change
INF = float('inf')

Q = deque([vi])

DP = [INF]*(N+1)
ans = [-1]*(N)
l = [0]

def bisect(DP,a,l):
    if DP[0] >= a:
        if DP[0]==INF:
            l[0]+=1
        b = DP[0]
        DP[0] = a        
        return (0,b) 
    ok = 0
    ng = N
    while ng-ok>1:
        if DP[(ok+ng)//2]>=a:
            ng = (ok+ng)//2
        else:
            ok = (ok+ng)//2
    if DP[ng]==INF:
        l[0]+=1
    b = DP[ng]
    DP[ng] = a
    return (ng,b)


checked_list = [False]*N
checked_list[vi]=True

while len(Q)>0:
    v = Q.pop()
    if type(v)==type(0):
        Q.append(bisect(DP, A[v], l))
        ans[v] = l[0]
        for v1 in e_list[v]:
            if not checked_list[v1]:
                checked_list[v1]=True
                Q.append(v1)
    else:
        i,a = v
        DP[i] = a
        if a==INF:
            l[0]-=1
        
print(*ans, sep = "\n")

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
FourNb=[(1,0),(-1,0),(0,1),(0,-1)];EightNb=[(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('EWNS',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=0):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.size=len(ls)+1
                self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls,index=index)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.size
        self.ETout=[-1]*self.size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]

class SparseTable: # O(N log N) for init, O(1) for query(l,r)
    def __init__(self,ls,init_func=min,init_idl=float('inf')):
        self.func=init_func
        self.idl=init_idl
        self.size=len(ls)
        self.N0=self.size.bit_length()
        self.table=[ls[:]]
        self.index=[list(range(self.size))]
        self.lg=[0]*(self.size+1)
        
        for i in range(2,self.size+1):
            self.lg[i]=self.lg[i>>1]+1

        for i in range(self.N0):
            tmp=[self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) for j in range(self.size)]
            tmp_id=[self.index[i][j] if self.table[i][j]==self.func(self.table[i][j],self.table[i][min(j+(1<<i),self.size-1)]) else self.index[i][min(j+(1<<i),self.size-1)] for j in range(self.size)]
            self.table+=[tmp]
            self.index+=[tmp_id]
    
    # return func of [l,r)
    def query(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        return self.func(self.table[N][l],self.table[N][r-(1<<N)])
    
    # return index of which val[i] = func of v among [l,r)
    def query_id(self,l,r):
        if r>self.size:r=self.size
        #N=(r-l).bit_length()-1
        N=self.lg[r-l]
        a,b=self.index[N][l],self.index[N][r-(1<<N)]
        if self.table[0][a]==self.func(self.table[N][l],self.table[N][r-(1<<N)]):
            b=a
        return b
    
    def __str__(self):
        return str(self.table[0])

    def print(self):
        for i in self.table:
            print(*i)

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

show_flg=False
show_flg=True
ans=0

n=I()
a=LI()
tr=Tree(n,index=1)

ET=tr.EulerTour(0)
dp=[inf]*n

def update(x):
    idx=bisect.bisect_left(dp,x)
    y=dp[idx]
    dp[idx]=x
    return idx,x,y
    
ans=[-1]*n
q=deque()
scnd=10**10
pre=-1
d=tr.ETdepth
for node,depth in zip(tr.ETtable,d):
    
    if depth>pre:
        idx,x,y=update(a[node])
        q.append((idx,x,y))
        if ans[node]==-1:
            ans[node]=bisect.bisect(dp,scnd)
    else:
        idx,x,y=q.pop()
        dp[idx]=y
    pre=depth

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import bisect
import sys


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


def dfs(v):
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        pos = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u)
    if pos == -1:
        dp.pop()
    else:
        dp[pos] = back


ans = [-1] * N
sys.setrecursionlimit(10 ** 6)
dp = []
dfs(0)


for an in ans:
    print(an)

Submission status: Accepted

Solution code:
import bisect
import sys


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

ans = [-1] * N


def dfs(v, dp):
    # dp は参照渡し
    if len(dp) == 0 or a[v] > dp[-1]:
        dp.append(a[v])
        back = -1
    else:
        pos = bisect.bisect_left(dp, a[v])
        back = dp[pos]
        dp[pos] = a[v]
    ans[v] = len(dp)

    for u in to[v]:
        if ans[u] == -1:
            dfs(u, dp)
    if back == -1:
        dp.pop()
    else:
        dp[pos] = back


sys.setrecursionlimit(10 ** 6)
dfs(0, [])


for an in ans:
    print(an)

Submission status: Accepted

Solution code:
import collections
import bisect
import sys

sys.setrecursionlimit(10 ** 8)

def f(v):
    state[v] = 1
    a=As[v]
    idx = bisect.bisect_left(D,a)
    stack.append( (idx,D[idx]) ) # push
    D[idx] = a
    
    ans[v] = bisect.bisect_left(D,float('inf'))

    for u in V[v]:
        if state[u] == 0:
            f(u)

    # 巻き戻し
    i_pre,d_pre=stack.pop()
    D[i_pre] = d_pre



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

D=[float('inf')]*N
stack=collections.deque([])
ans=[0]*N
state=[0]*N

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

f(0)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            if A[u] > LIS[-1]:
                LIS.append(A[u])
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS.pop()
            else:
                ind = bisect_left(LIS,A[u])
                stack = LIS[ind]
                LIS[ind] = A[u]
                ans[u] = len(LIS)
                dfs(u,LIS)
                LIS[ind] = stack
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2*10**5+100)
from bisect import *

def dfs(v, pv):
    j = bisect_left(dp, a[v])
    prev = dp[j]
    dp[j] = a[v]
    ans[v] = bisect_left(dp, 10**18)-1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs(nv, v)
    
    dp[j] = prev

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

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

dp = [10**18]*(N+1)
dp[0] = -10**18
ans = [-1]*N
dfs(0, -1)

for ans_i in ans:
    print(ans_i)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left
from collections import deque
import sys

sys.setrecursionlimit(10**9)

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = deque()
LIS.append(A[0])
ans = [0] * N

def dfs(v, p=-1):
    a = A[v]
    if a > LIS[-1]:
        idx = len(LIS) - 1
        old_val = -1
        LIS.append(a)
    else:
        idx = bisect_left(LIS, a)
        old_val = LIS[idx]
        LIS[idx] = a

    ans[v] = len(LIS)

    for u in G[v]:
        if u == p:
            continue
        dfs(u, v)
    
    if old_val == -1:
        LIS.pop()
    else:
        LIS[idx] = old_val

dfs(0)

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left
import sys

sys.setrecursionlimit(10**9)

def dfs(v, p=-1):
    a = A[v]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a

    ans[v] = bisect_left(LIS, INF)

    for u in G[v]:
        if u == p:
            continue
        dfs(u, v)
    
    LIS[idx] = old_val

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = [INF] * N
ans = [0] * N

dfs(0)

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

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left

INF = 10**9 + 1
N = int(input())
A = list(map(int, input().split()))
G = [[] for i in range(N)]
for i in range(N-1):
    u, v = list(map(int, input().split()))
    G[u-1].append(v-1)
    G[v-1].append(u-1)

LIS = [INF] * N
ans = [0] * N

stack = deque()
stack.append((0, None, None)) # (current_node, prev_node, old_val)
while stack:
    c_node, p_node, old_val = stack.pop()

    if c_node == -1:
        LIS[p_node] = old_val
        continue

    a = A[c_node]
    idx = bisect_left(LIS, a)
    old_val = LIS[idx]
    LIS[idx] = a 
    
    ans[c_node] = bisect_left(LIS, INF)

    stack.append((-1, idx, old_val))

    for next_node in G[c_node]:
        if next_node != p_node:
            stack.append((next_node, c_node, old_val))

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from bisect import bisect_left
def resolve():
    N = ir()
    a = lr()
    tr = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = lr()
        tr[u-1].append(v-1)
        tr[v-1].append(u-1)
    INF = pow(10, 9)+1
    lis = [INF]*N
    lis[0] = a[0]
    ans = [0]*N
    ans[0] = 1
    def dfs(v, p=-1):
        for u in tr[v]:
            if u == p:
                continue
            idx = bisect_left(lis, a[u])
            prev = lis[idx]
            lis[idx] = a[u]
            ans[u] = bisect_left(lis, INF)
            dfs(u, v)
            lis[idx] = prev
    dfs(0)
    print(*ans, sep='\n')
resolve()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(10**7)
INF=10**10

changed=[]
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split())) 
g=[[] for i in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)
LIS=[INF]*n

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, a[i])
    changed.append((changeID, LIS[changeID]))
    LIS[changeID] = min(a[i], LIS[changeID])
    Ans[i] = bisect_left(LIS, INF) 
    for nextN in g[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backID, backV = changed.pop()
    LIS[backID] = backV
    return 0

def main():
    Ans=[1]*n
    dfs(0,0,Ans)
    for i in Ans:
        print(i)
    
    return 0

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def solve(G, a, lis, pre, p, ans):
    target = a[p]
    idx = bisect_left(lis, target)
    frm = lis[idx]
    to = target
    lis[idx] = to
    ans[p] = bisect_left(lis, float("inf"))
    for v in G[p]:
        if v == pre:
            continue
        solve(G, a, lis, p, v, ans)
    lis[idx] = frm

def main():
    n = int(input())
    a = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        G[u].append(v)
        G[v].append(u)
    lis = [float("inf")]*(n+1)
    ans = [None]*n
    solve(G, a, lis, -1, 0, ans)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
import sys
import bisect

INF = 1145141919

a = []
dp = []
ans = []
T = []


def dfs(v: int, p: int):
    index = bisect.bisect_left(dp, a[v])
    dp[index], a[v] = a[v], dp[index]

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

    for u in T[v]:
        if u != p:
            dfs(u, v)

    dp[index], a[v] = a[v], dp[index]


def solve(N: int, tmp_a: "List[int]", tmp_T: "List[List[int]]"):
    sys.setrecursionlimit(10 ** 6)

    global dp, ans, a, T
    dp = [INF] * N
    ans = [0] * N
    a = tmp_a
    T = tmp_T

    dfs(0, -1)

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


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    T = [[] for _ in range(N)]  # type: "List[List[int]]"
    for i in range(N - 1):
        u = int(next(tokens)) - 1
        v = int(next(tokens)) - 1
        T[u].append(v)
        T[v].append(u)
    solve(N, a, T)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
n = int(input())
*A, = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    G[x - 1].append(y - 1)
    G[y - 1].append(x - 1)
inf = 10**10
DP = [inf for i in range(n)]
L = [0 for i in range(n)]
V = [False for i in range(n)]
Q = [(0, -1)]
while Q:
    x, a = Q.pop()
    if a == -1:
        V[x] = True
        i = bisect.bisect_left(DP, A[x])
        Q.append((i, DP[i]))
        DP[i] = A[x]
        L[x] = bisect.bisect_left(DP, inf)
        for y in G[x]:
            if not V[y]:
                Q.append((y, -1))
    else:
        DP[x] = a
print(*L, sep='\n')

Submission status: Accepted

Solution code:
import bisect
n = int(input())
*A, = map(int, input().split())
G = [[] for i in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    G[x - 1].append(y - 1)
    G[y - 1].append(x - 1)
inf = 10**10
DP = [inf for i in range(n)]
L = [0 for i in range(n)]
Q = [(-1, 0, None)]
while Q:
    p, x, b = Q.pop()
    if x == -1:
        DP[p] = b
        continue
    i = bisect.bisect_left(DP, A[x])
    Q.append((i, -1, DP[i]))
    DP[i] = A[x]
    L[x] = bisect.bisect_left(DP, inf)
    for y in G[x]:
        if y != p:
            Q.append((x, y, None))
print(*L, sep='\n')

Submission status: Accepted

Solution code:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10**5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))
    node = {i: [] for i in range(n)}

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

    ans = [0] * n
    dp = [INF] * n
    dp[0] = a[0]
    visited = [False] * n

    from collections import deque
    import bisect

    def dfs(cur):
        visited[cur] = True
        nv = a[cur]
        index = bisect.bisect_left(dp, nv)
        pv = dp[index]
        dp[index] = nv
        suc = node[cur]

        for nx in suc:
            if not visited[nx]:
                dfs(nx)

        ans[cur] = bisect.bisect_left(dp, INF)
        dp[index] = pv

    dfs(0)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from sys import setrecursionlimit

setrecursionlimit(3*10**5)

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    T[u].add(v)
    T[v].add(u)

search = [0]*N

A = [INF]*N

ans = [-1]*N

def dfs(V):
    num = a[V]
    num = a[V]
    k = bisect_left(A,num)
    v = A[k]
    A[k] = num
    ans[V] = bisect_left(A,INF)
    for VV in T[V]:
        if search[VV]:
            continue
        search[VV] = 1
        dfs(VV)
    A[k] = v

search[0] = 1
dfs(0)

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

Submission status: Accepted

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

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    T[u].add(v)
    T[v].add(u)

search = [0]*N

A = [INF]

ans = [-1]*N

def dfs(V):
    num = a[V]
    added = 0
    if A[-1] < num:
        A.append(num)
        added = 1
    else:
        k = bisect.bisect_left(A,num)
        v = A[k]
        A[k] = num
    ans[V] = len(A)
    for VV in T[V]:
        if search[VV]:
            continue
        search[VV] = 1
        dfs(VV)
    if added:
        A.pop()
    else:
        A[k] = v

search[0] = 1
dfs(0)

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

Submission status: Accepted

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

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    T[u].add(v)
    T[v].add(u)

search = [0]*N

A = [INF]*N

ans = [-1]*N

def dfs(V):
    num = a[V]
    k = bisect.bisect_left(A,num)
    v = A[k]
    A[k] = num
    ans[V] = bisect.bisect_left(A,INF)
    # このにぶたん無駄じゃね？まあ間に合うからいいか……
    for VV in T[V]:
        if search[VV]:
            continue
        search[VV] = 1
        dfs(VV)
    A[k] = v

search[0] = 1
dfs(0)

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

Submission status: Accepted

Solution code:
from collections import deque
import bisect
import sys

sys.setrecursionlimit(200000)

N = int(input())
a = list(map(int, input().split()))
uvs = [list(map(int, input().split())) for _ in range(N-1)]
shortest = [10e+10 for _ in range(N)]
shortest[0] = 0

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

for uv in uvs:
    routes[uv[0]-1].append(uv[1]-1)
    routes[uv[1]-1].append(uv[0]-1)

lis = [10e+100 for _ in range(N)]
minimum = [10e+100 for _ in range(N)]
seen = [False for _ in range(N)]
seen[0] = True

def function(checking):
    insert_posi = bisect.bisect_left(lis, a[checking])
    preserved = lis[insert_posi]
    lis[insert_posi] = a[checking]
    minimum[checking] = bisect.bisect_left(lis, 10e+50)
    for route in routes[checking]:
        if seen[route] == False:
            seen[route] = True
            shortest[route] = shortest[checking]+1
            function(route)
    lis[insert_posi] = preserved
    return
        
function(0)

[print(x) for x in minimum]

Submission status: Accepted

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

def main():
    N = int(input())
    A = tuple(map(int, input().split()))

    to = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        to[a].append(b)
        to[b].append(a)
    
    # bfs
    INF = 10 ** 18
    dp = [INF] * N
    ans = [0] * N

    def dfs(s):
        stack = deque()
        pop = stack.pop
        push = stack.append

        push((s, -1, None))

        while stack:
            now, pre, old = pop()

            # 復元
            if now == -1:
                dp[pre] = old
                continue
            
            a = A[now]
            idx = bisect_left(dp, a)
            old = dp[idx]
            dp[idx] = a

            ans_idx = bisect_left(dp, INF)
            ans[now] = ans_idx

            # 復元用 頂点
            # (フラグ, 変更したidx, 前の値)
            push((-1, idx, old))
            
            for nv in to[now]:
                if nv != pre:
                    push((nv, now, None))
    
    dfs(0)
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left
sys.setrecursionlimit(1000000)
INF = pow(10, 10)

changed = []
input = sys.stdin.readline
N = int(input())
A = [int(a) for a in input().split()]
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    Edge[u-1].append(v-1)
    Edge[v-1].append(u-1)
LIS = [INF] * N

def dfs(i, pre, Ans):
    changeID = bisect_left(LIS, A[i])
    changed.append((changeID, LIS[changeID]))
    LIS[changeID] = min(A[i], LIS[changeID])
    #print(i, LIS)
    #print(changed)
    Ans[i] = bisect_left(LIS, INF) 
    for nextN in Edge[i]:
        if nextN != pre: dfs(nextN, i, Ans)
    backID, backV = changed.pop()
    LIS[backID] = backV
    return 0

def solve():
    Ans = [1] * N
    dfs(0, 0, Ans)
    print("\n".join(map(str, Ans)))
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from bisect import bisect_left
from collections import defaultdict as dd
N = int(input())
As = list(map(int, input().split()))
Es = dd(dict)
for _ in range(N-1):
    f, t = map(int, input().split())
    Es[f-1][t-1] = Es[t-1][f-1] = 1

INF = float('inf')
RET = 0
PROC = 1

stack = []
lismin = [INF] * N
anss = [INF] * N
visited = [False] * N

stack.append((RET, 0, INF))
stack.append((PROC, 0, 0))
while stack:
    cmd, *v = stack.pop()
    if cmd == RET:
        i, backup = v
        lismin[i] = backup
    else:
        node, i = v
        lismin[i] = As[node]
        anss[node] = bisect_left(lismin, INF)
        visited[node] = True
        for to in Es[node].keys():
            if not visited[to]:
                x = bisect_left(lismin, As[to])
                stack.append((RET, x, lismin[x]))
                stack.append((PROC, to, x))
for ans in anss:
    print(ans)