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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(set())
        self.use(value)
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        for d in self.history[-1]:
            self.dp[d.dp_key] = d.before_value

    def use(self, value):
        for length, last_value in enumerate(self.dp):
            if last_value is math.inf:
                break
            if last_value < value:
                self.update_dp(length + 1, value)


    def update_dp(self, length, value):
        if value < self.dp[length]:
            self.history[-1].add(SolverLIS.Diff(length, self.dp[length]))
            self.dp[length] = value



    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

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








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    a=list(map(int,input().split()))
    edge=[[] for _ in range(N)]
    for _ in range(N-1):
        x,y=map(int1,input().split())
        edge[x].append(y)
        edge[y].append(x)
    stack=[(0,1)]
    used=[False]*N
    ans=[0]*N
    dpdp=[[0]+[INF]*(N+10)]
    prev_l=1
    while stack:
        v,l=stack.pop()
        used[v]=True
        for _ in range(prev_l-l):
            dpdp.pop()
        prev_l=l
        dp=dpdp[-1][:]
        dp[bisect_right(dp,a[v]-1,hi=l)]=a[v]
        ans[v]=bisect_left(dp,INF,hi=l+1)-1
        f=True
        for nv in edge[v]:
            if not used[nv]:
                if f:
                    dpdp.append(dp)
                    f=False
                stack.append((nv,l+1))
    for a in ans:
        print(a)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append(set())
        self.use(value, len(self.dp))
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        for d in self.history[-1]:
            self.dp[d.dp_key] = d.before_value

    def use(self, value, loop_end):
        for length, last_value in enumerate(self.dp[:loop_end + 1]):
            if last_value < value:
                self.update_dp(length + 1, value)


    def update_dp(self, length, value):
        if value < self.dp[length]:
            self.history[-1].add(SolverLIS.Diff(length, self.dp[length]))
            self.dp[length] = value



    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef):
        # process
        ans[node] = solver.append_last(node_values[node])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node)
        # exit recursive
        solver.remove_last()
    _dps(1, 0)
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

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








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
sys.setrecursionlimit(10 ** 7)
from pprint import pprint as pp
from pprint import pformat as pf


import math

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    class Diff:
        def __init__(self, dp_key, before_value):
            self.dp_key = dp_key
            self.before_value = before_value

    def __init__(self):
        self.dp = [0] # var[length] = min value
        self.history = [None] # var[node_id] = Diff # var[0] is dummy

    def append_last(self, value):
        self.dp.append(math.inf)
        self.history.append([])
        self.use(value, len(self.dp))
        return self.get_longest_increasing_subsequence_size()

    def remove_last(self):
        self.undo()
        self.dp.pop(-1)
        self.history.pop(-1)

    def undo(self):
        for d in self.history[-1]:
            self.dp[d.dp_key] = d.before_value

    def use(self, value, loop_end):
        for length, last_value in enumerate(self.dp[:loop_end + 1]):
            if last_value < value:
                self.update_dp(length + 1, value)


    def update_dp(self, length, value):
        if value < self.dp[length]:
            self.history[-1].append(SolverLIS.Diff(length, self.dp[length]))
            self.dp[length] = value



    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def iter_node_value(path, node_values):
    for node in path:
        yield node_values[node]

def dps(node_values, edges):
    solver = SolverLIS()
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef, path):
        path.append(node)
        # process
        value_list = list(iter_node_value(path, node_values))
        #print('value_list, node') # debug
        #print(value_list, node) # debug
        #ans[node] = longest_increment_size(value_list)
        ans[node] = solver.append_last(value_list[-1])
        # recursive
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node, path)
        # exit recursive
        solver.remove_last()
        path.pop(-1)
    _dps(1, 0, [])
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

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








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from pprint import pprint as pp
from pprint import pformat as pf

import math

class SolverLIS:
    """
    solver = SolverLIS(data)
    ans = solver.run()
    """

    def __init__(self, seq):
        self.seq = seq #TODO assert: element > 0
        self.dp = [math.inf] * (len(seq) + 1) # var[length] = min value
        self.dp[0] = 0

    def run(self):
        for i, value in enumerate(self.seq):
            self.use(value, i)
        #print('self.dp') # debug
        #print(self.dp) # debug
        return self.get_longest_increasing_subsequence_size()

    def use(self, value, loop_end):
        for length, last_value in enumerate(self.dp[:loop_end + 1]):
            if last_value < value:
                self.update_dp(length + 1, value)


    def update_dp(self, length, value):
        self.dp[length] = min(self.dp[length], value)



    def get_longest_increasing_subsequence_size(self):
        length = len(self.dp) - 1
        while length >= 0:
            value = self.dp[length]
            if value is not math.inf and value > 0:
                return length
            # for next
            length -= 1
        return 0


class Edges:

    def __init__(self, num_node):
        self.data = [None] * (num_node + 1) # var[frm] = to # 0 is dummy
        for i, _ in enumerate(self.data):
            self.data[i] = set()

    def register(self, frm, to):
        self.data[frm].add(to)
        self.data[to].add(frm)

    def get(self, frm):
            return self.data[frm]

    def __repr__(self):
        out = ""
        for i, s in enumerate(self.data):
            out += "{}:{}".format(i, s.__repr__())
        return out

def iter_node_value(path, node_values):
    for node in path:
        yield node_values[node]

def dps(node_values, edges):
    ans = [None] * (len(node_values)) # [last_node] = path, [0] is dummy. ref. node_values[0] is also dummy
    #print('ans') # debug
    #print(len(ans)) # debug
    def _dps(node, bef, path):
        path.append(node)
        # process
        value_list = list(iter_node_value(path, node_values))
        #print('value_list, node') # debug
        #print(value_list, node) # debug
        #ans[node] = longest_increment_size(value_list)
        ans[node] = SolverLIS(value_list).run()
        # go next
        for to in edges.get(node):
            if to == bef:
                continue
            _dps(to, node, path)
        path.pop(-1)
    _dps(1, 0, [])
    return ans


if __name__ == '__main__':
    n = int(input())
    node_values = list(map(int, input().split()))
    node_values.insert(0, 0) # dummy
    edges = Edges(n)
    for i in range(n - 1):
        e = list(map(int, input().split()))
        edges.register(*e)
    #print('edges') # debug
    #print(edges) # debug
    path_list = dps(node_values, edges)
    #print('path_list') # debug
    #print(path_list) # debug
    #print(len(path_list)) # debug

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








    #print('\33[32m' + 'end' + '\033[0m')

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
a = LI()
edges = [[] for _ in range(n)]
dp = [10**10]*n
for _ in range(n-1):
    u,v = LI()
    edges[u-1].append(v-1)
    edges[v-1].append(u-1)

ans = [None]*n
ans[0] = 1
dp[0] = a[0]
def dfs(k, p, dp):
    flag = False
    for v in edges[k]:
        if v != p:
            l = bl(dp, a[v])
            if dp[l] > a[v]:
                idx = l
                tmp = dp[l]
                dp[l] = a[v]
                flag = True
            ans[v] = n - dp.count(10**10)
            dfs(v, k, dp)
            if flag:
                dp[idx] = tmp
                flag = False
    return 
dfs(0, -1, dp)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


from bisect import bisect_left, bisect_right, insort_left


class BinarySearchTree:
    def __init__(self, ls: list = []):
        '''
        C++でいうsetを実装する。二分探索木をガチで実装しようとすると大変なので、ここでは配列二分法を用いる。
        pythonの標準ライブラリがヨイショに抱っこしてくれるおかげで楽に実装できる。
        https://docs.python.org/ja/3/library/bisect.html
        ls ... 渡す初期配列
        '''
        self.bst = ls  # insertをO(1)にするためにlistの代わりにdequeを用います

    def __repr__(self):
        return f'BST:{self.bst}'

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

    def __getitem__(self, idx):
        return self.bst[idx]

    def size(self):
        return len(self.bst)

    def insert(self, x):
        insort_left(self.bst, x)

    def remove(self, x):
        '''
        xを取り除く。xがself.bstに存在することを保証してください。
        同一のものが存在した場合は左から消していく
        '''
        del self.bst[self.find(x)]

    def bisect_left(self, x):
        '''
        ソートされた順序を保ったまま x を self.bst に挿入できる点を探し当てます。
        lower_bound in C++
        '''
        return bisect_left(self.bst, x)

    def bisect_right(self, x):
        '''
        bisect_left() と似ていますが、 self.bst に含まれる x のうち、どのエントリーよりも後ろ(右)にくるような挿入点を返します。
        upper_bound in C++
        '''
        return bisect_right(self.bst, x)

    def find(self, x):
        '''
        xのidxを探索
        '''
        idx = bisect_left(self.bst, x)
        if idx != len(self.bst) and self.bst[idx] == x:
            return idx
        raise ValueError

    def insert_replace_left(self, x):
        '''
        xを挿入して、xの左の数字(次に小さい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) - 1
        if idx_del + 1 == 0:  # xがどの要素よりも小さい
            self.insert(x)
        if idx_del < len(self.bst):
            self.insert(x)
            del self.bst[idx_del]

    def insert_replace_right(self, x):
        '''
        xを挿入して、xの右の数字(次に大きい)を削除する。idxがはみ出す場合は挿入だけ
        '''
        idx_del = self.bisect_left(x) + 1
        if idx_del - 1 == len(self.bst):  # xがどの要素よりも大きい
            self.insert(x)
        else:
            self.insert(x)
            del self.bst[idx_del]


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd

# 各ノードに今までの最長増加部分列と現在の増加部分列長の記録があれば、たかだた分岐地点から探索できるのでは？
N = read_a_int()
A = read_ints()
Tree = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v = read_ints()
    u -= 1
    v -= 1
    Tree[u].append(v)
    Tree[v].append(u)

LIS = BinarySearchTree([-1])

ans = [-1] * N


def dfs(u, p, LIS):  # これって参照渡しに成るんすかねすると厄介かもしれない
    '''現在のノード、親、最長増加部分列の状態'''
    LIS.insert_replace_right(A[u])
    ans[u] = len(LIS) - 1
    # print(u, LIS.bst)
    if len(Tree[u]) > 2 or u == 0:  # 配列のコピーを渡す
        for nu in Tree[u]:
            if nu == p:
                continue
            dfs(nu, u, BinarySearchTree(LIS.bst.copy()))  # ここでTLE
    elif len(Tree[u]) == 2:  # 参照渡しでok
        for nu in Tree[u]:
            if nu == p:
                continue
            dfs(nu, u, LIS)


# def dfs(u, p, LIS):  # これって参照渡しに成るんすかねすると厄介かもしれない
#     '''現在のノード、親、最長増加部分列の状態'''
#     LIS.insert_replace_right(A[u])
#     ans[u] = len(LIS) - 1
#     for nu in Tree[u]:
#         if nu == p:
#             continue
#         dfs(nu, u, BinarySearchTree(LIS.bst.copy()))


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue_append = queue.append
    queue_append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            tmp_append = tmp.append
            A_now = A[i]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A_now > tmp[-1]:
                tmp_append(A_now)
            else:
                tmp[bisect.bisect_left(tmp, A_now)] = A_now
            queue_append((i,tmp))
            ans[i] = len(tmp)

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

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue.append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A[i] > tmp[-1]:
                tmp.append(A[i])
            else:
                tmp[bisect.bisect_left(tmp, A[i])] = A[i]
            queue.append((i,tmp))
            ans[i] = len(tmp)

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

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left, bisect_right
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    repn = [[] for _ in range(N)]
    for _ in range(N - 1):
        u, v = map(int, input().split())
        repn[u - 1].append(v - 1)
        repn[v - 1].append(u - 1)
    
    length = [0] * (N + 1)
    dp = [-1]

    """
    やはり各頂点でLIS配列を取ると配列コピーの時間がかかってTLEするので、
    配列は唯一つを扱って、DFSからバックするときに配列も元に戻す操作を行いたい
    （ここの実装の仕方がわからなかった）

    これはdfsを再帰で書いた後に復元操作を追記すれば異常に楽に書ける。。。
    """

    def dfs(v, p=N):
        if A[v] > dp[-1]:
            dp.append(A[v])
            length[v] = length[p] + 1
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp.pop()
        else:
            length[v] = length[p]
            idx = bisect_left(dp[:length[p]], A[v]) # bisect_rightだとdpに重複する値を書き込んでしまうのでダメ
            old = dp[idx]
            dp[idx] = A[v]
            for u in repn[v]:
                if u == p: continue
                dfs(u, v)
            dp[idx] = old
        #print("v={}, len={}, dp={}".format(v, length[v], dp))

    dfs(0)
    length.pop()
    for ans in length:
        print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
aa = {}
j = 0
for i in [int(i) for i in input().split()]:
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
    j += 1
a = [0] * n
k = 1
for i in sorted(list(aa)):
    for j in aa[i]:
        a[j] = k
    k += 1


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[r - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([0] * (max(a)+10), max, 0)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1):

    y = seg.get_segment(0, a[i])
    ans1[i] = y + 1
    ans2[i] = max(ans2[r], ans1[i])

    be = seg.get_item(a[i])
    seg.update_func(a[i], ans1[i])
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
    seg.update(a[i], be)


dfs()
print("\n".join(map(str,(ans2))))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


n = int(input())
aa = {}
j = 0
for i in [int(i) for i in input().split()]:
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
    j += 1
a = [0] * n
k = 1
for i in sorted(list(aa)):
    for j in aa[i]:
        a[j] = k
    k += 1


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        if self.b[i] != x:
            return
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[r - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


e = [[] for _ in range(n)]
for _ in range(n - 1):
    aa, bb = [int(i) - 1 for i in input().split()]
    e[aa].append(bb)
    e[bb].append(aa)
seg = SegmentTree([0] * (max(a)+10), max, 0)
ans1 = [0] * n
ans1[0] = 1
ans2 = [0] * n
ans2[0] = 1


def dfs(i=0, r=-1):

    y = seg.get_segment(0, a[i])
    ans1[i] = y + 1
    ans2[i] = max(ans2[r], ans1[i])

    be = seg.get_item(a[i])
    seg.update_func(a[i], ans1[i])
    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)
    seg.update(a[i], be)


dfs()
for i in ans2:
    print(i)