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:
import bisect
import collections

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
q=collections.deque()
q.append((1,1,[arr[1]]))
while len(q)!=0:
  v,l,tr=q.popleft()
  ans[v]=l
  for u in g[v]:
    if checked[u]==0:
      checked[u]=1
      pos=bisect.bisect_left(tr,arr[u])
      if pos==l:
        q.append((u,l+1,tr+[arr[u]]))
      elif tr[pos]==arr[u]:
        q.append((u,l,tr))
      else:
        q.append((u,l,tr[:pos]+[arr[u]]+tr[pos+1:]))
for i in range(1,n+1):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces


#ダイクストラ(参照:https://gside.org/blog/2019/12/01/, https://ta7uw.hatenablog.com/entry/2018/09/30/222102)
class Node(object):#頂点
    def __init__(self,  value: int):
        self.value = value

    def getValue(self) -> int:
        return self.value

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

    def __lt__(seif, other):
        return None


class WeightedEdge(object):#重み付き枝
    def __init__(self, src: Node, dest: Node, weight: int):
        self.src = src
        self.dest = dest
        self.weight = weight

    def getSource(self) -> Node:
        return self.src

    def getDestination(self) -> Node:
        return self.dest

    def getWeight(self) -> int: 
        return self.weight

    def __str__(self):
        return str(self.src.getValue()) + '->('  + str(self.getWeight()) + ')->' + str(self.dest.getValue())


class Digraph(object):#有向グラフ
    def __init__(self):
        self.nodes = []
        self.edges = {}
        self.size = 0

    def addNode(self, node: Node):
        if node in self.nodes:
            raise ValueError('Duplicate node')
        else:
            self.nodes.append(node)
            self.edges[node] = []
            self.size += 1
    
    def addEdge(self, edge: WeightedEdge):
        src = edge.getSource()
        dest = edge.getDestination()
        weight = edge.getWeight()
        if not (src in self.nodes and dest in self.nodes):
            raise ValueError('Node not a graph')

        self.edges[src].append((weight, dest))
    
    def childrenOf(self, node: Node) -> list:#element : tuple
        return self.edges[node]
    
    def __str__(self):
        result = ''
        for src in self.nodes:
            for weightdest in self.edges[src]:
                dest  = weightdest[1]
                result += str(src.getValue()) + '->' + str(dest.getValue()) + '\n'
        return result[:-1]


class RingBuffer(object):
    def __init__(self, size: int):
        self.ringsize = size
        self.size = 0
        self.ring = [None]*size
        self.head = 0
        self.tail = 0
    def enring(self, a: int):
        if self.tail != self.head or self.ring[self.tail] == None:
            self.ring[self.tail] = a
            self.tail += 1
            self.tail %= self.ringsize
            self.size += 1
        else:
            print('Error : This Ring Buffer is full.')
    def dering(self):
        if self.head != self.tail:
            tmp = self.ring[self.head]
            self.ring[self.head] = None # なくてもよい．
            self.head += 1
            self.head %= self.ringsize
            self.size -= 1
            return tmp
        else:
            print(self.head, self.tail)
            print('Error : This Ring Buffer is empty.')


def getPath(goalNode, prev):
    path = [goalNode]
    dest = goalNode.getValue()
    while prev[dest] != float('inf'):
        path.append(prev[dest])
        dest = prev[dest].getValue()
    return list(reversed(path))


def Dijkstra(graph: Digraph, startNode: Node, goalNode: Node = None) -> list:#Reture a list that has minimum distances from the start point to each point
    dist = [float('inf') for _ in range(graph.size)]
    prev = [float('inf') for _ in range(graph.size)]

    dist[startNode.getValue()] = 0
    srcque = RingBuffer(graph.size)
    costque = RingBuffer(graph.size)
    
    srcque.enring(startNode)
    costque.enring(0)
    while srcque.size != 0:
        srcNode = srcque.dering()
        prev_cost = costque.dering()

        if dist[srcNode.getValue()] < prev_cost:
            continue
        
        for cost, destNode  in graph.childrenOf(srcNode):
            if cost != float('inf') and dist[destNode.getValue()] > dist[srcNode.getValue()] + cost:
                dist[destNode.getValue()] = dist[srcNode.getValue()] + cost
                srcque.enring(destNode)
                costque.enring(dist[destNode.getValue()])
                prev[destNode.getValue()] = srcNode
    if goalNode == None:
        return dist
    else:
        return getPath(goalNode, prev)


import bisect

def my(seq):
    LIS = [seq[0]]
    for i in range(len(seq)):
        if seq[i] > LIS[-1]:
            LIS.append(seq[i])
        else:
            LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
    return len(LIS)

def main():
    n = ni()
    As = na()
    d = Digraph()
    Nodes = [Node(i) for i in range(n)]
    for node in Nodes:
        d.addNode(node)
    for _ in range(n-1):
        u,v = na()
        d.addEdge(WeightedEdge(Nodes[u-1],Nodes[v-1],1))
        d.addEdge(WeightedEdge(Nodes[v-1],Nodes[u-1],1))
    for k in range(n):
        dist = Dijkstra(d, Nodes[0], Nodes[k])
        ss = [As[node.getValue()] for node in dist]
        print(my(ss))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=-1):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = -1
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current, diffs):
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, -1))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            diffs = child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val == -1:
                current.pop()
            else:
                current[index] = val
        return diffs


root = Tree(0)
root.dp([], [])
for i in range(N):
    print(trees[i].ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=None):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = -1
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current, diffs):
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, -1))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            diffs = child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val == -1:
                current.pop()
            else:
                current[index] = val
        return diffs


root = Tree(0)
root.dp([], [])
for i in range(N):
    print(trees[i].ans)

Submission status: Time Limit Exceeded

Solution code:

MOD = 10 ** 9 + 7

def main():
    for _ in inputt(1):
        n,  = inputi()
        P = [[] for _ in range(n + 1)]
        R = [1] * (n + 1)
        A = [0] + inputl()
        for _ in range(n - 1):
            a, b = inputi()
            P[a].append(b)
            P[b].append(a)
        Z = [0] * (n + 1)
        def T(i, D):
            if not Z[i]:
                Z[i] = 1
                nD = D.copy()
                for d, v in D:
                    if A[i] > v:
                        if d + 1 < len(D):
                            nD[d + 1] = min(nD[d + 1], (d + 1, A[i]))
                        else:
                            nD.append((d + 1, A[i]))
                R[i] = nD[-1][0]
                for p in P[i]:
                    T(p, nD)
        T(1, [(0, -inf)])
        print(*R[1:], split="\n")


# region M


# region import

from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(200100)

# endregion

# region fastio

BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.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(io.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")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    print("debug", *args, **kwargs)
    sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda k = int: map(k, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())

# endregion

# region bisect

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError

# endregion

# region csgraph
# TODO

class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass

# endregion

# region ntheory

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            self.extend_to_no(n.stop + 1)
            return self._list[n.start: n.stop: n.step]
        else:
            self.extend_to_no(n + 1)
            return self._list[n]

sieve = Sieve()
def isprime(n):
    if n <= sieve._list[-1]:
        return n in sieve
    for i in sieve:
        if not n % i: return False
        if n < i * i: return True
prime = sieve.__getitem__
primerange = lambda a, b = 0: sieve.primerange(a, b) if b else sieve.primerange(2, a)
def factorint(n):
    factors = []
    for i in sieve:
        if n < i * i: break
        while not n % i:
            factors.append(i)
            n //= i
    if n != 1: factors.append(n)
    return factors
factordict = lambda n: Counter(factorint(n))

# endregion

# region main

if __name__ == "__main__":
    main()

# endregion


# endregion

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


def lmi():
    return list(map(int, input().split()))


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())

a = lmi()

adj = collections.defaultdict(set)
uv = llmi(N - 1)
for _u, _v in uv:
    u, v = _u - 1, _v - 1
    adj[u].add(v)
    adj[v].add(u)

trees = {}


class Tree:
    def __init__(self, index, parent_index=None):
        self.val = a[index]
        self.index = index
        self.parent = parent_index
        self.adj = []
        for v in adj[index]:
            if v == parent_index:
                continue
            self.adj.append(Tree(v, parent_index=self.index))
        self.ans = None
        trees[index] = self

    def __repr__(self):
        return '{}: {}'.format(self.index, [t.val for t in self.adj])

    def dp(self, current, diffs):
        v = bisect.bisect_left(current, self.val)
        if v >= len(current):
            diffs.append((v, None))
            current.append(self.val)
        else:
            diffs.append((v, current[v]))
            current[v] = self.val
        self.ans = len(current)
        for child_tree in self.adj:
            diffs = child_tree.dp(current, diffs)
            index, val = diffs.pop()
            if val is None:
                current.pop()
            else:
                current[index] = val
        return diffs


root = Tree(0)
root.dp([], [])
for i in range(N):
    print(trees[i].ans)

Submission status: Time Limit Exceeded

Solution code:
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)] for i in range(n)]
dp[0][0] = -1
used = [0 for i in range(n)]
used[0] = 1

queue = [0]
while queue:
    pos = queue.pop()
    idx = bisect(dp[pos], al[pos] - 1)
    dp[pos][idx] = min(al[pos], dp[pos][idx])
    ansl[pos] = max(i for i in range(n+1) if dp[pos][i] < float("inf"))
    for v in G[pos]:
        if used[v] == 0:
            used[v] = 1
            dp[v] = dp[pos][:]
            queue.append(v)



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

Submission status: Time Limit Exceeded

Solution code:
import math
import bisect
from collections import deque

N=int(input())
a=list(map(int,input().split()))
u=[]
v=[]
road=[[] for i in range(N)]
for i in range(N-1):
  u1,v1=map(int,input().split())
  road[u1-1].append(v1-1)
  road[v1-1].append(u1-1)
  
#幅優先探索BFSか
ans=[0]*N
houmon=[0]*N
s=deque([])
s.append(0)
dp=[[] for i in range(N)]
dp[0].append(a[0])
while(s):
  v=s.popleft()
  for x in road[v]:#vから行ける場所x
    if(houmon[x]==0):
      dp[x].extend(dp[v])
      s.append(x)
      dp[x].append(a[x])
  houmon[v]=1
  #print(dp)
for i in range(N):
  seq=dp[i]
  #print(seq)
  LIS = [seq[0]]
  for i in range(len(seq)):
    if seq[i] > LIS[-1]:
      LIS.append(seq[i])
    else:
      LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
  print(len(LIS))

Submission status: Time Limit Exceeded

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

from collections import deque
from bisect import bisect_left

ans = [0] * N

que = [(0, [A[0]] + [float("inf")])]
ans[0] = 1

while que:
    v, dp = que.pop()
    for w in edge[v]:
        if ans[w]: continue
        dp2 = dp[:]
        idx = bisect_left(dp2, A[w])
        dp2[idx] = A[w]
        ans[w] = bisect_left(dp2, float("inf"))
        if dp2[-1] != float("inf"):
            dp2.append(float("inf"))
        que.append((w, dp2))


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

Submission status: Time Limit Exceeded

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

n = int(input())

a_l = 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)

q = deque()


ans = [0 for i in range(n)]

seen = [0 for i in range(n)]
q.append([0, [0]])
seen[0] = 1

while len(q):
    cur = q.popleft()

    node_num = cur[0]
    prev_lis = copy.deepcopy(cur[1])

    cur_a = a_l[node_num]

    if cur_a > prev_lis[-1]:
        prev_lis.append(cur_a)
    else:
        prev_lis[bisect_left(prev_lis, cur_a)] = cur_a

    ans[node_num] = len(prev_lis) - 1

    for next in tree[node_num]:
        if seen[next] == 0:
            q.append([next, prev_lis])
            seen[next] = 1

for i in range(n):
    print(ans[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
from collections import deque


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

from numba import jit


@jit
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 io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
sys.setrecursionlimit(10**6)
N=int(input())
A=[0]+list(map(int,input().split()))

E=[[] for i in range(N+1)]
for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

USE=[0]*(N+1)
USE[1]=1
ANS=[0]*(N+1)

import bisect
def dfs(x,DP):
    #print(x,DP)
    pos=bisect.bisect_left(DP,A[x])
    #print(pos)
    if pos<len(DP):
        DP=list(DP)
        DP[pos]=A[x]
        DP=tuple(DP)
    else:
        DP+=(A[x],)
    #print(DP)

    ANS[x]=len(DP)

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            dfs(to,DP)

dfs(1,tuple())

print(*ANS[1:])

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)
    dp = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    dp[0] = [A[0]]
    B[0] = [A[0]]
    queue = deque([0])
    while queue:
        now = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append(i)
            B[i] = B[now] + [A[i]]
            dp[i] += dp[now]
            if B[i][-1] > dp[i][-1]:
                dp[i].append(B[i][-1])
            else:
                dp[i][bisect.bisect_left(dp[i], B[i][-1])] = B[i][-1]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import bisect
from copy import copy

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)

d= deque()
INF=10010001001
dpinit = [a[0]]
d.append((0,-1,copy(dpinit)))
ansls=[0]*n
ansls[0]=1
while d:
    u,p,dp = d.popleft()
    for v in to[u]:
        if v==p:
            continue
        idx=bisect.bisect_left(dp,a[v])
        if idx<len(dp):
            prv=dp[idx]
            dp[idx]=a[v]       
        else:
            dp.append(a[v])
            prv=-1
        ansls[v]=len(dp)
        d.append((v,u,copy(dp)))
        if prv!=-1:
            dp[idx]=prv
        else:
            dp.pop()


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

Submission status: Time Limit Exceeded

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

import bisect

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

g=[[] for i in range(n)]

for x,y in a1:
    g[x-1].append(y-1)
    g[y-1].append(x-1)


vis = [0] * n
order = []
parent = [0] * n
s = [0]

while len(s):
    x = s.pop()
    vis[x] = 1
    order.append(x)
    for y in g[x]:
        if vis[y]: continue
        s.append(y)
        parent[y] = x


ans=[0]*n
LIS = [[0] for i in range(n)]

for x in order:
    LIS[x]=LIS[parent[x]][:]
    if a[x] > LIS[x][-1]:
        LIS[x].append(a[x])
    else:
        LIS[x][bisect.bisect_left(LIS[x], a[x])] = a[x]
    ans[x]=len(LIS[x])-1

for i in ans:
    print(i)