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:
def main():
    from bisect import bisect_left
    import sys
    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [inf] * N

    def dfs(v, p=-1):
        i = bisect_left(lis, a[v])
        prev_at_i = lis[i]
        lis[i] = a[v]
        ans[v] = bisect_left(lis, inf)
        for u in g[v]:
            if p == u: continue
            dfs(u, v)
        lis[i] = prev_at_i

    dfs(0)

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す

Submission status: Accepted

Solution code:
def main():
    from bisect import bisect_left
    import sys
    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    inf = 1 << 30

    N = int(input())
    *a, = map(int, input().split())

    g = tuple(set() for _ in range(N))
    for _ in range(N - 1):
        u, v = (int(x) - 1 for x in input().split())
        g[u].add(v)
        g[v].add(u)

    ans = [0] * N
    lis = [inf] * N
    lis[0] = a[0]

    def dfs(v, p=-1):
        ans[v] = bisect_left(lis, inf)
        for u in g[v]:
            if p == u: continue
            i = bisect_left(lis, a[u])
            prev_at_i = lis[i]
            lis[i] = a[u]
            dfs(u, v)
            lis[i] = prev_at_i

    dfs(0)

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


if __name__ == '__main__':
    main()

# dp[i]=長さiの増加部分列の末尾としてありえる最小値
# というテーブルを持っておいて、数列を列を前から見ながら二分探索で更新箇所を探す

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)

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

inf = 10 ** 10
d = [inf for _ in range(n)]
dp = [inf for _ in range(n)]

def dfs(cur, prev):
    memo = bisect.bisect_left(dp, a[cur])
    memo_v = dp[memo]
    dp[memo] = a[cur]
    d[cur] = bisect.bisect_left(dp, inf)

    for to in edges[cur]:
        if to != prev:
            dfs(to, cur)

    dp[memo] = memo_v

dfs(0, -1)
for i in range(n):
    print(d[i])

Submission status: Accepted

Solution code:
import sys
import bisect
sys.setrecursionlimit(10**9)
INF = 2**30
N = int(input())
A = list(map(int, input().split()))
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    u, v = list(map(int, input().split()))
    u -= 1
    v -= 1
    E[u].append(v)
    E[v].append(u)

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

def dfs(now, par, len):
    ok = bisect.bisect_left(dp, A[now])
    memo = dp[ok]
    dp[ok] = A[now]

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

    for to in E[now]:
        if to == par:
            continue
        dfs(to, now, len+1)
    dp[ok] = memo

dfs(0, -1, 0)

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

Submission status: Accepted

Solution code:
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
INF = float('inf')

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

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

ans = [0] * n
dp = [INF] * n
dp[0] = a[0]
# dp[i] = (長さi+1の増加部分列の最終項のmin)


def dfs(v, v_p):
    ans[v] = bisect_left(dp, INF)

    for v_next in graph[v]:
        if v_next == v_p:
            continue

        idx = bisect_left(dp, a[v_next])
        past = dp[idx]
        dp[idx] = a[v_next]
        dfs(v_next, v)
        dp[idx] = past


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

Submission status: Accepted

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

def main():
    n=int(input())
    A=list(map(int, input().split()))
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        u,v=map(int,input().split())
        u-=1; v-=1
        Edges[u].append(v)
        Edges[v].append(u)
    LIS=[10**11]*n
    Ans=[0]*n

    def dfs(v,par):
        idx=bisect_left(LIS,A[v])
        tmp=LIS[idx]
        LIS[idx]=A[v]
        Ans[v]=bisect_left(LIS,10**10)
        for chi in Edges[v]:
            if chi==par:
                continue
            dfs(chi,v)
        LIS[idx]=tmp

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

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1
#print(AA, a2f)

R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
stack = [1]
visited = set([1])
path = []
while stack:
    v = stack.pop()
    if v > 0:
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
#        print(v, qq)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            visited.add(u)
            stack += [-v, u]
    else:
        c = path.pop()
        ss.update(AA[c], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Accepted

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


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

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)

Submission status: Accepted

Solution code:
import bisect


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

edges = [[] for _ in range(n+1)]
for _ in range(n-1):
    from_, to = map(int, input().split())
    edges[from_].append(to)
    edges[to].append(from_)


DP = [10**9+7] * (n+1)
limit = 10**9 + 1
DP[0] = 0
olds = [None] * (n+1)
ans = [0] * n

todo = [1]
while todo:
    node = todo.pop()
    if node > 0:
        num = A[node-1]
        update_idx = bisect.bisect_left(DP, num)
        old = DP[update_idx]
        olds[node] = (old, update_idx)
        DP[update_idx] = num
        lis = bisect.bisect_left(DP, limit) - 1
        ans[node-1] = lis

        todo.append(-node)
        for to in edges[node]:
            if ans[to-1]:
                continue
            todo.append(to)

    else:
        node = -node
        old, update_idx = olds[node]
        DP[update_idx] = old

for res in ans:
    print(res)

Submission status: Accepted

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

import sys
input = sys.stdin.readline

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

from collections import defaultdict
G = defaultdict(list)

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

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


stack = []
def dfs(pos):
    idx = bisect(dp, al[pos] - 1)
    stack.append((idx, dp[idx]))
    dp[idx] = min(al[pos], dp[idx])
    ansl[pos] = bisect(dp, 10**18) - 1
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dfs(v)
            idx, k = stack.pop()
            dp[idx] = k


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

Submission status: Accepted

Solution code:
import bisect,sys

input=sys.stdin.readline
sys.setrecursionlimit(1000000)

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

dp=[10**20 for i in range(N)]
ans=[-1 for i in range(0,N)]
def dfs(v,pv):
    pos=bisect.bisect_left(dp,a[v])
    prev=dp[pos]
    dp[pos]=a[v]
    ans[v]=bisect.bisect_left(dp,10**18)
    for i in edge[v]:
        if i==pv:
            continue

        dfs(i,v)

    dp[pos]=prev

dfs(0,-1)
for i in range(N):
    print(ans[i])

Submission status: Accepted

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

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

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


ans = [0] * N
ans[0] = 1
INF = 10**10
dp = [INF] * N
dp[0] = A[0]
stack = []
n_stack = []
def dfs(node, par, n):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    n_stack.append(n)
    dp[idx] = num
    n = max(n, idx + 1)
    ans[child] = n
    dfs(child, node, n)
    # 巻き戻し
    idx, num = stack.pop()
    dp[idx] = num
    n = n_stack.pop()

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

Submission status: Accepted

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

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

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


ans = [0] * N
ans[0] = 1
INF = 10**10
dp = [INF] * N
dp[0] = A[0]
stack = []
def dfs(node, par, n):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    dp[idx] = num
    ans[child] = max(n, idx+1)
    # ans[child] = bisect.bisect_left(dp, INF)
    dfs(child, node, max(n, idx+1))
    # 巻き戻し
    idx, num = stack.pop()
    dp[idx] = num

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

Submission status: Accepted

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

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

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


ans = [0] * N
ans[0] = 1
INF = 10**10
dp = [INF] * N
dp[0] = A[0]
stack = []
def dfs(node, par):
  global ans
  global dp
  global stack
  children = tree[node]
  for child in children:
    if child == par:
      continue
    num = A[child]
    idx = bisect.bisect_left(dp, num)
    stack.append([idx, dp[idx]])
    dp[idx] = num
    ans[child] = bisect.bisect_left(dp, INF)
    dfs(child, node)
    # 巻き戻し
    idx, num = stack.pop()
    dp[idx] = num

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

Submission status: Accepted

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

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

lis = [float('inf')] * n
ans = [0] * n

def dp(v, prev):
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for u in G[v]:
        if u != prev:
            dp(u, v)
    lis[i] = tmp

dp(0, -1)
for l in ans:
    print(l)

Submission status: Accepted

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    par = {root: -1}
    stack = [root]
 
    while stack:
        v = stack.pop()
        if v >= 0:  # 行きがけ順の処理
            trail.append(v)
            stack.append(~v)
            for nxt_v in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append(nxt_v)
 
        else:  # 帰りがけ順の処理
            if ~v == root:
                continue
            trail.append(-par[~v])
 
    return trail


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

tree = [[] for i in range(n)]
for u, v in info:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

res = euler_tour(tree, 0)
array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if ind > 0:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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

Submission status: Accepted

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

def dfs(v):
  pos=bisect.bisect_left(dp,arr[v])
  changes.append((pos,dp[pos]))
  dp[pos]=arr[v]
  ans[v]=bisect.bisect_left(dp,10**18)
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      dfs(u)
  pos,val=changes.pop()
  dp[pos]=val

n=int(input())
arr=[0]+list(map(int,input().split()))
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
ans=[0]*(n+1)
checked=[0]*(n+1)
checked[1]=1
dp=[10**18 for _ in range(n+1)]
changes=[]
dfs(1)
for i in range(1,n+1):
  print(ans[i])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
import bisect
INF = 10**10

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

ans = [0] * n
lis = [INF] * n
def dfs(p, v):
    place = bisect.bisect_left(lis, a[v])
    val = lis[place]
    lis[place] = a[v]
    ans[v] = bisect.bisect_left(lis, INF)
    for nv in edge[v]:
        if nv == p:
            continue
        dfs(v, nv)
    lis[place] = val

dfs(-1, 0)
for item in ans:
    print(item)

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1
#print(AA, a2f)

R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
ss.update(AA[1], 1)
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        c = path.pop()
        ss.update(AA[c], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Accepted

Solution code:
from bisect import bisect_left


def solve(n, a_list, uv_list):
    res = [0] * n
    tree = [[] for _ in range(n)]
    for u, v in uv_list:
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)

    # euler tour
    visited = [0] * n
    parent = [-1] * n
    tour = [0]
    p = 0
    while True:
        visited[p] = 1
        r = parent[p]
        while len(tree[p]):
            q = tree[p].pop()
            if visited[q] == 0:
                parent[q] = p
                r = q
                break
        if r == -1:
            break
        p = r
        tour.append(p)
    # assert len(tour) == 2 * n - 1
    # print(tour)

    # tree DP
    dp = [10 ** 9 + i for i in range(n + 1)]
    dp[0] = 0
    re_visited = [0] * n
    callbacks = []
    for p in tour:
        if re_visited[p] == 0:
            re_visited[p] = 1
            ind = bisect_left(dp, a_list[p])
            callbacks.append((ind, dp[ind]))
            dp[ind] = a_list[p]
            res[p] = bisect_left(dp, 10 ** 9) - 1
        else:
            ind, v = callbacks.pop()
            dp[ind] = v
        # print(dp)
    # print(res)
    return res


def main():
    n = int(input())
    a_list = list(map(int, input().split()))
    uv_list = [list(map(int, input().split())) for _ in range(n - 1)]
    res = solve(n, a_list, uv_list)
    for r in res:
        print(r)


def test():
    assert solve(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]]
                 ) == [1, 2, 3, 3, 4, 4, 5, 2, 2, 3]
    assert solve(10, [5, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [1, 10]]
                 ) == [1, 1, 1, 1, 1, 2, 2, 1, 1, 1]
    assert solve(10, [5, 2, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 1, 2, 2, 2, 2, 2, 2, 1, 2]
    assert solve(10, [3, 5, 5, 3, 4, 6, 7, 3, 2, 4],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 2, 2, 2, 2, 3, 3, 2, 2, 2]
    assert solve(10, [3, 3, 3, 3, 3, 3, 3, 3, 3, 3],
                 [[1, 2], [2, 3], [2, 4], [2, 5], [2, 6], [2, 7], [2, 8], [2, 9], [2, 10]]
                 ) == [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]


if __name__ == "__main__":
    test()
    main()

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

#ライブラリインポート
from collections import defaultdict
import bisect
INF = float("inf")

#入力受け取り
def getlist():
	return list(map(int, input().split()))


class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

def Euler_tour(G, node, visit, DP, prev, ans, A):
	for i in G.graph[node]:
		if visit[i] != "Yes":
			visit[i] = "Yes"
			#LIS更新
			x = bisect.bisect_left(DP, A[i])
			prev.append([x, DP[x]])
			DP[x] = A[i]
			ans[i] = bisect.bisect_left(DP, INF)
			# print(DP, i)
			# print(prev)
			Euler_tour(G, i, visit, DP, prev, ans, A)

	#LIS戻す
	x, val = prev.pop()
	DP[x] = val

#処理内容
def main():
	N = int(input())
	A = getlist()
	G = Graph()
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)

	#DFS初期化
	DP = [INF] * N
	DP[0] = A[0]
	prev = [[0, A[0]]]
	ans = [None] * N
	ans[0] = 1
	visit = ["No"] * N
	visit[0] = "Yes"
	Euler_tour(G, 0, visit, DP, prev, ans, A)
	for i in range(N):
		print(ans[i])


if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        # k+1ではなくkでは？
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res
from collections import defaultdict
import sys;input=sys.stdin.readline
N, = map(int, input().split())

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

iA = [(i, a) for i, a in enumerate(A)]
iA.sort(key=lambda x:x[1])
d = dict()
AA = [0]*(N+1)
a2f = [0]*(N+1)
rj = 0
for j, (i, a) in enumerate(iA):
    AA[i] = j
    if a not in d:
        rj = j
    a2f[i] = rj
    d[a] = 1
#print(AA, a2f)

R = [0]*(N+1)
R[1] = 1
ss = SegTree([0]*(N+1), N+1, -1, max)
ss.update(AA[1], 1)
stack = []
for u in G[1]:
    stack += [-1, u]
visited = set([1])
path = [1]
while stack:
    v = stack.pop()
    if v > 0:
        visited.add(v)
        path.append(v)
        qq = ss.query(0, a2f[v])
        ss.update(AA[v], qq+1)
        R[v] = ss.query(0, N+1)
        for u in G[v]:
            if u in visited:
                continue
            stack += [-v, u]
    else:
        child = path.pop()
        ss.update(AA[child], 0)
for i in range(1, N+1):
    print(R[i])

Submission status: Accepted

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

n=int(input())
a=list(map(int,input().split()))
g = [[]for _ 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 = [float('inf')]*n
ans = [0]*n

def dfs(now, pre):
    idx = bisect_left(lis, a[now])
    tmp = lis[idx]
    lis[idx] = a[now]
    ans[now] = bisect_left(lis, float('inf'))
    for to in g[now]:
        if to == pre:
            continue
        dfs(to, now)
    lis[idx] = tmp

dfs(0,-1)
for x in ans:
    print(x)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

INF = float('inf')

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

dp = [-INF]
anss = [0] * N
def dfs(vNow, vPar):
    A = As[vNow]
    if dp[-1] < A:
        dp.append(A)
        tp = 0
    else:
        i = bisect_left(dp, A)
        tp = 1
        iOld, AOld, = i, dp[i]
        dp[i] = A
    anss[vNow] = len(dp)-1

    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        dfs(v2, vNow)

    if tp == 0:
        dp.pop()
    else:
        dp[iOld] = AOld

dfs(0, -1)

print('\n'.join(map(str, anss)))

Submission status: Accepted

Solution code:
from collections import deque
import bisect
import sys
sys.setrecursionlimit(500000)

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

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

INF=1001001001
dp = [INF]*n
dp[0]=a[0]
ansls=[0]*n
ansls[0]=1
history=deque()
def dfs(u,p,rank):
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        prv=dp[idx]
        dp[idx]=a[v]       
        history.append((idx,prv))
        ansls[v]=bisect.bisect_left(dp,INF)
        dfs(v,u,rank+1)
        while len(history)>rank:
            idx,prv =history.pop()
            dp[idx] = prv

dfs(0,-1,0)

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

Submission status: Accepted

Solution code:

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

import sys
sys.setrecursionlimit(max(1000, 2*n))


ns = defaultdict(set)
for _ in range(n-1):
    u,v = [int(c) for c in input().split()]
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

from bisect import bisect_left
 
l = [a[0]]
# for a in A[1:]:
#     if a > L[-1]:
#         # Lの末尾よりaが大きければ増加部分列を延長できる
#         L.append(a)
#     else:
#         # そうでなければ、「aより小さい最大要素の次」をaにする
#         # 該当位置は、二分探索で特定できる
#         L[bisect_left(L, a)] = a
# return len(L)

ans = [None] * n

def sub(u, prev, lst, old, ind, ans):
    aa = a[u]
    if len(lst)==0 or aa > lst[-1]:
        lst.append(aa)
        old = -1
        ind = None
    else:
        ind = bisect_left(lst, aa)
        old = lst[ind]
        lst[ind] = aa
    ans[u] = len(lst)
#     print(lst)
    for v in ns[u]:
        if prev==v:
            continue
        sub(v, u, lst, old, ind, ans)
    if old==-1:
        lst.pop()
    elif old is not None:
        lst[ind] = old

lst = []
sub(0, -1, lst, None, None, ans)
print("\n".join(map(str, ans)))

Submission status: Accepted

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

N = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * N
ans = [0] * N

def dfs(v, p):
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
    lis[i] = tmp

dfs(0, -1)
print('\n'.join(map(str, ans)))

Submission status: Accepted

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

N = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(N)]
for _ in range(N-1):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    G[u].append(v)
    G[v].append(u)
lis = [float('inf')] * N
ans = [0] * N
visited = [False] * N

def dfs(v):
    visited[v] = True
    i = bisect_left(lis, a[v])
    tmp = lis[i]
    lis[i] = a[v]
    ans[v] = bisect_left(lis, float('inf'))
    for c in G[v]:
        if visited[c]:
            continue
        dfs(c)
    lis[i] = tmp

dfs(0)
print('\n'.join(map(str, ans)))