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:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")

#solve
def solve():
    def dfs(x):
        ans[x] = bisect_left(dp, inf)
        for e in edg[x]:
            if d[e]:
                d[e] = 0
                i = bisect_left(dp, a[e])
                p = dp[i]
                dp[i] = a[e]
                dfs(e)
                dp[i] = p
    n = II()
    a = LI()
    dp = [inf] * n
    edg = [[] for i in range(n)]
    for _ in range(n - 1):
        u, v = LI_()
        edg[u].append(v)
        edg[v].append(u)
    d = [1] * n
    ans = [1] * n
    d[0] = 0
    dp[0] = a[0]
    dfs(0)
    for a in ans:
        print(a)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
import bisect

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

N = int(input())

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

F = [-1 for _ in range(N)]
F[0] = 1
INF = 10 ** 9
dp = [INF for _ in range(N + 1)]
dp[0] = A[0]


def dfs(s):
    for d in T[s]:
        if F[d] == -1:
            t = bisect.bisect_left(dp, A[d])
            p = dp[t]
            dp[t] = A[d]
            F[d] = bisect.bisect_left(dp, INF)
            dfs(d)
            dp[t] = p


dfs(0)

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

Submission status: Accepted

Solution code:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7
INT_MAX = 10**9
# MOD = 998244353


N = read_item()
vals = read_n_item()
graph = defaultdict(list)

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

ans = [0] * N
ans[0] = 1
dp = [vals[0]]


def dfs(cur, pre):
    ans[cur] = len(dp)

    for nxt in graph[cur]:
        if nxt == pre:
            continue
        i = bisect_left(dp, vals[nxt])
        if i < len(dp):
            temp = dp[i]
            dp[i] = vals[nxt]
            dfs(nxt, cur)
            dp[i] = temp
        else:
            dp.append(vals[nxt])
            dfs(nxt, cur)
            dp.pop()


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

Submission status: Accepted

Solution code:
n=int(input())
l=[0]+list(map(int,input().split()))
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
s=1
ans=[0 for i in range(n+1)]

from bisect import bisect_left, bisect_right
INF=float('inf')

import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
def dfs(s,d,c):
    dep[s]=d
    x=bisect_left(c,l[s])
    c[x],y=l[s],c[x]
    ans[s]=bisect_left(c,INF)
    for i in edge[s]:
        if dep[i]==-1:
            dfs(i,d+1,c)
    c[x]=y
c=[INF]*len(l)
dfs(1,0,c)
for i in range(1,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left

sys.setrecursionlimit(10 ** 6)


def dfs(v, p, links, state, ans):
    ans[v] = len(state)
    for u in links[v]:
        if u == p:
            continue
        a = aaa[u]
        b, i = -1, -1
        if state[-1] < a:
            state.append(a)
        else:
            i = bisect_left(state, a)
            b = state[i]
            state[i] = a
        dfs(u, v, links, state, ans)
        if b == -1:
            state.pop()
        else:
            state[i] = b


n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in range(n)]
for line in sys.stdin:
    u, v = map(int, line.split())
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)
ans = [0] * n
dfs(0, -1, links, [aaa[0]], ans)
print('\n'.join(map(str, ans)))

Submission status: Accepted

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

from bisect import bisect_left

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

INF = 10 ** 10

adj = [[] for _ in range(n)]
for u, v in uv:
    u -= 1
    v -= 1
    adj[u].append(v)
    adj[v].append(u)

arrived = [False] * n

ans = [None] * n
ans[0] = 1

dp = [INF] * n


def dfs(u):
    arrived[u] = True
    for v in adj[u]:
        if not arrived[v]:
            idx = bisect_left(dp, a[v])
            tmp = dp[idx]
            dp[idx] = a[v]
            ans[v] = bisect_left(dp, INF - 1)
            dfs(v)
            dp[idx] = tmp


dp[0] = a[0]
dfs(0)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

import sys
sys.setrecursionlimit(10**7)

class RangeMinimumQuery:
    def __init__(self, n):
        self.n0 = 2**(n-1).bit_length()
        self.data = [0]*(2*self.n0)

    def query(self, l,r):
        l += self.n0
        r += self.n0
        res = 0
        while l < r:
            if r&1:
                r -= 1
                res = max(res, self.data[r-1])
            if l&1:
                res = max(res, self.data[l-1])
                l += 1
            l >>=1
            r >>=1
        return res

    def update(self, i, x):
        i += self.n0-1
        self.data[i] = x
        while i:
            i = ~-i//2
            self.data[i] = max(self.data[2*i+1], self.data[2*i+2])


n = int(input())
a = list(map(int, input().split()))
d = {j:i for i,j in enumerate(sorted(set(a)))}
m = len(d)
a = [d[i] for i in a]

G = [[] for i in range(n)]
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)

RMQ = RangeMinimumQuery(m+10)
ans = [0]*n
def dfs(cur, prev):
    ai = a[cur]
    now = RMQ.query(ai, ai+1)
    nxt = max(RMQ.query(0, ai)+1, now)
    RMQ.update(ai, nxt)
    ans[cur] = RMQ.query(0, m+1)
    for to in G[cur]:
        if to != prev:
            dfs(to, cur)
    RMQ.update(ai, now)
dfs(0,-1)

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

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
inf = 10**12
minf = 10**11
pre = [inf for _ in range(n)]
pst = [[] for _ in range(n)]
right = [inf for _ in range(n)]
seen = [0 for _ in range(n)]
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        now.append(y)
        seen[y] = 1
        pre[y] = x
        right[y] = x
        if pst[x]:
          right[pst[x][-1]] = y
        pst[x].append(y)
down = [i for i in range(n)]
for i in range(n):
  if pst[i]:
    down[i] = pst[i][0]
#print(pre)
#print(right)
#print(pst)
#print(down)
seen = [0 for _ in range(n)]
import bisect
lis = [inf for _ in range(n)]
rec = [[] for _ in range(n)]
now = 0
ans = [0 for _ in range(n)]
while True:
  if seen[now] == 0:
    seen[now] += 1
    #print(A[now],lis)
    b = bisect.bisect_left(lis,A[now])
    rec[now] = [b,lis[b]]
    lis[b] = A[now]
    ans[now] = bisect.bisect_left(lis,minf)
    now = down[now]
  else:
    seen[now] += 1
    b,c = rec[now]
    lis[b] = c
    if now == 0:
      break
    now = right[now]
for x in ans:
  print(x)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase

def lb(a,x):
    l,r=0,len(a)
    while r-l>1:
        m=(l+r)//2
        if a[m]<x:
            l=m
        else:
            r=m
    return r

class FenwickTree:
    def __init__(self, n):
        """transform list into BIT"""
        self.bit = [ [0] for _ in range(n) ]

    def update(self, idx, fl,x):
        """updates bit[idx] += x"""
        while idx < len(self.bit):
            if fl:
                self.bit[idx].append(max(x,self.bit[idx][-1]))
            else:
                self.bit[idx].pop()
            idx |= idx + 1

    def query(self, end):
        """calc sum(bit[:end])"""
        x = 0
        while end:
            x = max(x,self.bit[end - 1][-1])
            end &= end - 1
        return x


def dfs(graph, start,a):
    n = len(graph)

    dp = [0] * n
    visited, finished = [False] * n, [False] * n

    tree=FenwickTree(n+5)
    b=[]

    stack = [start]
    while stack:
        start = stack[-1]
        
        # push unvisited children into stack
        if not visited[start]:

            tree.update(a[start],True,1+tree.query(a[start]))
            dp[start]=tree.query(n+1)
            b+=[a[start]]
            # print(start,b,dp[start])

            visited[start] = True
            for child in graph[start]:
                if not visited[child]:
                    stack.append(child)

        else:
            stack.pop()
            b.pop()
            #pop start.
            tree.update(a[start],False,0)
            finished[start] = True

    return dp

def main():
    n=int(input())
    a=[int(x) for x in input().split()]
    b=[x for x in a]
    b.append(-1)
    b.append(10**9+1)
    b.sort()
    for i in range(len(a)):
        a[i]=lb(b,a[i])
    e=[[] for _ in range(n)]
    # print(e)
    for _ in range(n-1):
        u,v=map(int,input().split())
        e[u-1].append(v-1)
        e[v-1].append(u-1)
        
    # print(e)
    print(*dfs(e,0,a))

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**6)
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())
  u-=1;v-=1
  G[u].append(v)
  G[v].append(u)
dp = [inf] * (n+10)
dp[0] = A[0]
length = 1
fixed = [-1] * (n+10)
ans = [0] * n
def dfs(node,pre,length):
  if node != 0:
    if dp[length-1] < A[node]:
      dp[length] = A[node]
      length += 1
      fixed[node] = inf
    else:
      fixed[node] = dp[bisect.bisect_left(dp,A[node])]
      dp[bisect.bisect_left(dp,A[node])] = A[node]
  ans[node] = length
  for v in G[node]:
    if v == pre:continue
    dfs(v,node,length)
  dp[bisect.bisect_left(dp,A[node])] = fixed[node]

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

def LIS(seq):
    dp = [inf]*(n+10)
    dp[0] = seq[0]
    length = 1
    for i in range(1, n):
        if dp[length-1] < seq[i]:
            dp[length] = seq[i]
            length += 1
        else:
            dp[bisect.bisect_left(dp, seq[i])] = seq[i]
    return dp,length

Submission status: Accepted

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


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

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


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


def dfs(node):
    node = node
    num = A[node]
    update_idx = bisect.bisect_left(DP, num)
    prev = DP[update_idx]
    DP[update_idx] = num
    lis = bisect.bisect_left(DP, 10**9+1) - 1
    ans[node] = lis
    for nex in edges[node]:
        if not ans[nex]:
            dfs(nex)

    DP[update_idx] = prev


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

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    from bisect import bisect_left
    input = sys.stdin.buffer.readline

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

    que = deque()
    que.append(1)
    seen = [0] * (N+1)
    seen[1] = 1
    ans = [0] * (N+1)
    ans[1] = 1
    LIS = []
    change = [[] for _ in range(N+1)]
    while que:
        v = que.pop()
        if v > 0:
            que.append(-v)
            a = A[v-1]
            if not LIS:
                LIS.append(a)
                change[v] = (0, -1)
            else:
                j = bisect_left(LIS, a)
                if j == len(LIS):
                    LIS.append(a)
                    ans[v] = len(LIS)
                    change[v] = (len(LIS) - 1, -1)
                else:
                    change[v] = (j, LIS[j])
                    LIS[j] = a
                    ans[v] = len(LIS)
            for u in adj[v]:
                if seen[u] == 0:
                    seen[u] = 1
                    que.append(u)
        else:
            v = -v
            i, x = change[v]
            if x == -1:
                LIS.pop()
            else:
                LIS[i] = x
    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

import bisect
import sys
sys.setrecursionlimit(500000)

def LIS(lis):

    seq = []

    for c in lis:
        ind = bisect.bisect_left(seq,c)

        if ind == len(seq):
            seq.append(c)
        else:
            seq[ind] = c

    return len(seq)


N = int(input())

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

lis = [ [] for i in range(N) ]

for i in range(N-1):

    u,v = map(int,input().split())
    u -= 1
    v -= 1

    lis[u].append(v)
    lis[v].append(u)

ans = [None] * N

def dfs(v,p,ln):

    ind = bisect.bisect_left(ln,a[v])

    if ind == len(ln):
        mt = None
        ln.append(a[v])
    else:
        mt = ln[ind]
        ln[ind] = a[v]

    ans[v] = len(ln)

    for nex in lis[v]:

        if nex != p:
            dfs(nex,v,ln)

    if mt == None:
        del ln[-1]
    else:
        ln[ind] = mt

    return

dfs(0,0,[])

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

Submission status: Accepted

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

import sys, bisect
sys.setrecursionlimit(300000)


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[u[i] - 1].append(v[i] - 1)
        conns[v[i] - 1].append(u[i] - 1)

    ret = [-1] * N
    dp = []
    def dfs(idx):
        val = a[idx]
        k = -1
        if len(dp) == 0 or val > dp[-1]:
            dp.append(val)
        else:
            k = bisect.bisect_left(dp, val)
            tmp = dp[k]
            dp[k] = val
        ret[idx] = len(dp)
        for j in conns[idx]:
            if ret[j] >= 0:
                continue
            dfs(j)

        if k >= 0:
            dp[k] = tmp
        else:
            dp.pop()
        return
    dfs(0)
    for r in ret:
        print(r)
    return

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]"
    u = [int()] * (N - 1)  # type: "List[int]"
    v = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        u[i] = int(next(tokens))
        v[i] = int(next(tokens))
    solve(N, a, u, v)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N = int(input())
A = list(map(int,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)

visited = [False]*N
visited[0] = True
answer = [1]*N

def dfs(v, dp):
    for nv in Edge[v]:
        if visited[nv]:
            continue
        
        visited[nv] = True
        if len(dp)==0 or A[nv]>dp[-1]:
            dp.append(A[nv])
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp.pop()
        else:
            idx = bisect.bisect_left(dp, A[nv])
            temp = dp[idx]
            dp[idx] = A[nv]
            answer[nv] = len(dp)
            dfs(nv, dp)
            dp[idx] = temp
        
    return 

dfs(0, [A[0]])
answer[0] = 1
for a in answer:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect
from sys import setrecursionlimit

setrecursionlimit(10000000)

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


res = [None]*N
dp = [float('inf') for _ in range(N)]

def rec(v, ml):
    """
    dp[l]: min tail value of increasing subsequence of length l+1
    """
    a = A[v]
    i = bisect(dp, a-1)
    ml += int(ml == i)
    res[v] = ml

    orig = dp[i]
    dp[i] = a
    for u in adj[v]:
        if res[u] is None:
            rec(u, ml)
    dp[i] = orig

rec(0, 0)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter


def euler_tour(G, root=0):
    n = len(G)
    euler = []
    dq = deque([root])
    dq2 = deque()
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        for v in G[u]:
            if visited[v]:
                dq += [v]
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                dq2 += [v]
        dq.extend(dq2)
        dq2 = deque()
        visited[u] = 1
    return euler

import sys
import bisect
input = sys.stdin.readline
n = int(input())
num = list(map(int,input().split()))
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
et = euler_tour(graph,1)
vis = [0]*(n+1)
ans = [0]*(n+1)
dp = [0]
parent = [0]*(n+1)
dc = defaultdict(int)
for i in range(len(et)):
  x = et[i]
  m = num[x-1]
  if vis[x] == 0:
    if x != 1:
      parent[x] = et[i-1]
    idx = bisect.bisect_left(dp,m)
    if idx == len(dp):
      dp.append(m)
      dc[x] = -1
    else:
      dc[x] = dp[idx]
      dp[idx] = m
    ans[x] = len(dp)-1
    vis[x] = 1
  else:
    prv = num[et[i-1]-1]
    kid = et[i-1]
    change = dc[kid]
    idx = bisect.bisect_left(dp,prv)
    if change == -1:
      dp.pop()
    else:
      dp[idx] = change
print(*ans[1:])

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)

from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict
from itertools import combinations, permutations
from itertools import accumulate
from math import ceil, sqrt, pi

def LLL(a, ls):
    INF = 10 ** 15
    
    flag = 0
    prev = 0
    indx = 0
    ls_i = bisect_left(ls, a)
    if a < ls[ls_i]:
        flag = 1
        prev = ls[ls_i]
        indx = ls_i
    ls[ls_i] = min(ls[ls_i], a)

    ls_ii = bisect_left(ls, INF)
    return ls_ii, ls, flag, prev, indx

MOD = 10 ** 9 + 7
INF = 10 ** 18

N = int(input())
A = [0] + list(map(int, input().split()))
UV = [list(map(int, input().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N + 1)]
for uv in UV:
    u, v = uv
    graph[u].append(v)
    graph[v].append(u)
#print(graph)

INF = 10 ** 15

LIS = [INF for i in range(N + 2)]

answer = [0] * (N + 1)
def dfs(prev, n, LIS):
    answer[n], LIS, flag, prv, indx = LLL(A[n], LIS)
    #print(n, LIS, flag, prv, indx)
    for g in graph[n]:
        if g != prev:
            dfs(n, g, LIS)
    if flag:
        LIS[indx] = prv

dfs(-1, 1, LIS)

for a in answer[1:]:
    print(a)

Submission status: Accepted

Solution code:
from bisect import bisect_right
from sys import setrecursionlimit

setrecursionlimit(10**8)
n = int(input())
A = list(map(int, input().split()))
gr = []
for i in range(n):
    gr.append([])
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    gr[a].append(b)
    gr[b].append(a)
ans = [0] * n
dp = [10 ** 10 for i in range(1 + n)]
dp[0] = -10 ** 10
kek = 1
used = {0}


def dfs(v):
    global kek
    j = bisect_right(dp, A[v] - 1)
    old = dp[j]
    if dp[j - 1] < A[v] < dp[j]:
        old = dp[j]
        dp[j] = A[v]
        if kek == j:
            for h in range(kek + 1, 1 + n):
                if dp[h] == 10 ** 10:
                    kek = h
                    break
            if kek == j:
                kek = n + 1
    ans[v] = kek - 1
    for u in gr[v]:
        if u not in used:
            used.add(u)
            dfs(u)
    dp[j] = old
    if kek > j and old == 10 ** 10:
        kek = j


dfs(0)
print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
from bisect import bisect_left
def resolve():
    n = int(input())
    A = list(map(int,input().split()))
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    C = [INF] * (n + 1)
    res = -1
    ans = [None] * n
    change = [None] * n # 行きがけでの変更

    # DFS
    stack = [(0, -1)] # v, p
    while stack:
        v, p = stack.pop()
        if v >= 0:
            idx = bisect_left(C, A[v])
            res = max(res, idx)
            ans[v] = res + 1
            change[v] = (idx, C[idx])
            C[idx] = A[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            idx, prev = change[v]
            if prev == INF:
                res -= 1
            C[idx] = prev

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
INF = 10 ** 12
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 = [INF] * n
k = [None] * n
ans = [0] * n
s = [0]
while s:
    p = s.pop()
    if k[p] == None:
        s.append(p)
        idx = bisect_left(dp, a[p])
        k[p] = (idx, dp[idx])
        dp[idx] = a[p]
        ans[p] = bisect_left(dp, INF)
        for node in g[p]:
            if k[node] == None:
                s.append(node)
    else:
        idx, x = k[p]
        dp[idx] = x
for x in ans:
    print(x)

Submission status: Accepted

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

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

ans = [1]*n

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)

root = 0
chi = [[] for i in range(n)]
par = [-1]*n
used = [False]*n
tank = [0]

while tank:
    q = tank.pop()
    used[q] = True
    for e in edge[q]:
        if not used[e]:
            chi[q].append(e)
            tank.append(e)
            par[e] = q

tank = [root]

idx = dict()
val = dict()
dp = [10**10]*n

eulerNum = -1

while tank:
    q = tank.pop()
    if q >= 0:
        #first time
        num = a[q]
        kk = bisect.bisect_left(dp,num)
        
        val[q] = dp[kk]
        idx[q] = kk
        dp[kk] = num
        ans[q] = bisect.bisect_left(dp,10**10)

        eulerNum += 1
        tank.append(~q)
        for ch in chi[q]:
            tank.append(ch)
    else:
        if ~q != root:
            if dp[idx[~q]] == a[~q]:
                dp[idx[~q]] = val[~q]
                eulerNum += 1

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

Submission status: Accepted

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

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

# parent = [-1]*n
ans = [0]*n
def dfs(now,parent,LIS):
    w = bisect(LIS,a[now])
    if w > 0 and LIS[w-1] == a[now]:
        flag = -2
    elif w == len(LIS):
        flag = -1
        LIS.append(a[now])
    else:
        flag = w
        record = LIS[w]
        LIS[w] = a[now]
    ans[now] = len(LIS)
    for nxt in path[now]:
        if nxt == parent:continue
        dfs(nxt,now,LIS)
    if flag == -2:
        return
    elif flag == -1:
        LIS.pop()
    else:
        LIS[w] = record
    return
# stack = [0]
# LIS = [[] for _ in range(n)]
# while stack:
#     p = stack.pop()
#     if p == 0:
#         LIS[p] = [a[p]]
#     else:
#         parray = LIS[parent[p]].copy()
#         nxt = bisect(parray,a[p])
#         if nxt == len(parray):
#             LIS[p] = parray + [a[p]]
#         else:
#             parray[nxt] = a[p]
#             LIS[p] = parray
#     for to in path[p]:
#         if to == parent[p]:continue
#         parent[to] = p
#         stack.append(to)
dfs(0,-1,[])
print('\n'.join(str(i) for i in ans))