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:
N=int(input())
a=[int(x) for x in input().split()]
v=[]
for i in range(N-1):
    v.append([int(x) for x in input().split()])


m={}
m[0]=1
seen=[0]
unseen_v=v
seen_v=[]

def newlen(m,b_index,a_index):
    if a[b_index]<a[a_index]:
        return m[b_index]+1
    else:
        return m[b_index]

while unseen_v != []:
    for i in unseen_v:
        if i[0]-1 in m or i[1]-1 in m:
            if i[0]-1 in m:
                before=i[0]-1
                new=i[1]-1
            if i[1]-1 in m:
                before=i[1]-1
                new=i[0]-1

            seen.append(new)
            m[new]=newlen(m,before,new)
            seen_v.append(i)
            unseen_v.remove(i)
            
for i in range(N):
    print(m[i])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
ans = [1]*(n+1)
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    x = len(dp[b])
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        if dp[b][-1] < c:
            dp[i] = dp[b]+[c]
            ans[i] = x+1
        else:
            dp[i] = dp[b].copy()
            ans[i] = x
        for j in range(x-1,-1,-1):
            if j == 0 and dp[i][j] > c:
                dp[i][j] = c
            elif dp[i][j] > c and dp[i][j-1] < c:
                dp[i][j] = c
                
for i in ans[1:]:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)
    
stack = [1]
dp = [[] for _ in range(n+1)]
dp[1] = [a[0]]
checked = []
while stack:
    b = stack.pop()
    if b in checked:
        continue
    checked.append(b)
    x = len(dp[b])
    for i in t[b]:
        if i in checked:
            continue
        stack.append(i)
        c = a[i-1]
        if dp[b][-1] < c:
            dp[i] = dp[b]+[c]
        else:
            dp[i] = dp[b].copy()
        for j in range(x-1,-1,-1):
            if j == 0 and dp[i][j] > c:
                dp[i][j] = c
            elif dp[i][j] > c and dp[i][j-1] < c:
                dp[i][j] = c
                
for i in dp[1:]:
    print(len(i))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]
    dp2 = [0] * (N+1)
    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1

        if parent == None:
            dp[node].append(A[node])
            dp2[node] = 1
        else:
            dp2[node] = dp2[parent]
            a = A[node]
            done = False
            for i, val in enumerate(dp[parent][1:], 1):
                if val > a and not done:
                    if val == float('inf'):
                        dp2[node] += 1
                    dp[node].append(a)
                    done = True
                else:
                    dp[node].append(val)
            if dp[node][-1] < a:
                dp[node].append(a)
                dp2[node] += 1
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)

    for i in range(1, N+1):
        print(dp2[i])


if __name__ == "__main__":
    run()
    from time import time as TTT
    a = [0] * 10**5
    t1 = TTT()
    for _ in range(10**5):
        b = a.copy()
    t2 = TTT()
    print(t2-t1, 'sec')
    for _ in range(10**5):

        c = a[:]
    t3 = TTT()
    print(t3 - t2, 'sec')

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(x) for x in input().split()]
v=[]
for i in range(N-1):
    v.append([int(x) for x in input().split()])


m={}
m[0]=1
seen=[0]
unseen_v=v
seen_v=[]

def newlen(m,b_index,a_index):
    if a[b_index]<a[a_index]:
        return m[b_index]+1
    else:
        return m[b_index]

while unseen_v != []:
    for i in unseen_v:
        if i[0]-1 in m:
            new=i[1]-1
            seen.append(new)
            m[new]=newlen(m,i[0]-1,new)
            seen_v.append(i)
            unseen_v.remove(i)

           
    for i in unseen_v:
        if i[1]-1 in m:
            new=i[0]-1
            seen.append(new)
            m[new]=newlen(m,i[1]-1,new)
            seen_v.append(i)
            unseen_v.remove(i)
            
for i in range(N):
    print(m[i])

Submission status: Time Limit Exceeded

Solution code:
#!python3

import heapq


INF = 10 ** 10

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


def solve(link, w):
    l = [None] * N
    visit = [False] * N
    visit_n = 0
    # cost, len, node
    hq = [(0, -1, 0)]
    while hq:
        if visit_n == N:
            break
        c, n, v = heapq.heappop(hq)
        if visit[v] :
            continue
        visit[v] = True
        visit_n += 1
        l[v] = abs(n)
        for x in link[v]:
            if not visit[x]:
                heapq.heappush(hq, (c + 1, n + w[v][x], x))

    return l


def main():
    link = [[] for _ in range(N)]
    w = [[0] * N for _ in range(N)]
    for u, v in uv:
        u -= 1
        v -= 1
        link[u].append(v)
        link[v].append(u)
        if A[u] < A[v]:
            w[u][v] = -1
        if A[v] < A[u]:
            w[v][u] = -1
    
    l = solve(link, w)
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import heapq


INF = 10 ** 10

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


def solve(link, w):
    l = [None] * N
    visit = [False] * N
    visit_n = 0
    # cost, len, node
    hq = [(0, -1, 0)]
    while hq:
        if visit_n == N:
            break
        c, n, v = hq.pop()
        if visit[v] :
            continue
        visit[v] = True
        visit_n += 1
        l[v] = abs(n)
        for x in link[v]:
            if not visit[x]:
                heapq.heappush(hq, (c + 1, n + w[v][x], x))

    return l


def main():
    link = [[] for _ in range(N)]
    w = [[0] * N for _ in range(N)]
    for u, v in uv:
        u -= 1
        v -= 1
        link[u].append(v)
        link[v].append(u)
        if A[u] < A[v]:
            w[u][v] = -1
        if A[v] < A[u]:
            w[v][u] = -1
    
    l = solve(link, w)
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import heapq


INF = 10 ** 10

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


def solve(link, w):
    l = [None] * N
    visit = [False] * N
    # cost, len, node
    hq = [(0, -1, 0)]
    while hq:
        c, n, v = hq.pop()
        if visit[v] :
            continue
        visit[v] = True
        l[v] = abs(n)
        for x in link[v]:
            if not visit[x]:
                heapq.heappush(hq, (c + 1, n + w[v][x], x))

    return l


def main():
    link = [[] for _ in range(N)]
    w = [[0] * N for _ in range(N)]
    for u, v in uv:
        u -= 1
        v -= 1
        link[u].append(v)
        link[v].append(u)
        if A[u] < A[v]:
            w[u][v] = -1
        if A[v] < A[u]:
            w[v][u] = -1
    
    l = solve(link, w)
    for ans in l:
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [0] + lr()  # 1-indexed
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

answer = [0] * (N+1)  # 1-indexed
INF = 10 ** 10
parent = [-1] * (N+1)

def dfs(n, arr):
    """arrはLISのリスト、answerのリストを更新してから子にarrを渡す"""
    i = bisect_left(arr, INF)
    answer[n] = i
    for c in graph[n]:
        if c == parent[n]:
            continue
        parent[c] = n
        new = arr[:]
        i = bisect_left(new, A[c])
        new[i] = A[c]
        dfs(c, new)

B = [INF] * (N+1)
B[0] = A[1]
dfs(1, B)
for a in answer[1:]:
    print(a)

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, prev
    else:
        return getPath(goalNode, prev)


def BinarySearch(num, nums):
    if len(nums) == 0:
        print("Erorr : list has no element")
        return
    left,right = 0,len(nums)
    while left < right:
        mid  = (left+right)//2
        if num < nums[mid]:
            right = mid
        else:
            left = mid + 1
    return right


def LIS(seq):
    LISs = [seq[0]]
    for i in range(1,len(seq)):
        if seq[i] > LISs[-1]:
            LISs.append(seq[i])
        else:
            right = BinarySearch(seq[i], LISs)
            if LISs[right-1] != seq[i]:
                LISs[right] = seq[i]
    return len(LISs)
    

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))
    dist, prev = Dijkstra(d, Nodes[0])
    for k in range(n):
        ss = [As[node.getValue()] for node in getPath(Nodes[k], prev)]
        print(LIS(ss))
    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect

INF = 10 ** 10

N = int(input())
As = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(N-1)]

dfs_stack = [1]
ans = [-1] * N
lis = [INF] * (N+1)
rewinder = []

while dfs_stack:
    pos = dfs_stack.pop()
    for u, v in edges:
        if u == pos:
            if ans[v-1] == -1:
                dfs_stack.append(v)
            else:
                parent = v
        elif v == pos:
            if ans[u-1] == -1:
                dfs_stack.append(u)
            else:
                parent = u
    
    while rewinder:
        i, before, after = rewinder.pop()
        if after == As[parent-1]:
            rewinder.append( (i, before, after) )
            break
        else:
            lis[i] = before

    index = bisect.bisect_left(lis, As[pos-1])
    rewinder.append( (index, lis[index], As[pos-1]) )
    lis[index] = As[pos-1]
    ans[pos-1] = lis.index(INF)

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

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
a=[int(x) for x in input().split()]
v=[]
for i in range(N-1):
    v.append([int(x) for x in input().split()])


m={}
m[0]=1
current=[0]

while len(v) >0:
    
    indexes = [i for i, x in enumerate(v) if x[0]-1 in current]

    u=[]
    for i in indexes:
        new=v[i][1]-1
        u.append(v[i])

        

        
        if a[new] > a[v[i][0]-1]:
            m[new]=m[v[i][0]-1]+1
            current.append(new)
           
            
        else:
            m[new]=m[v[i][0]-1]
            current.append(new)
            
    for i in u:
        
        v.remove(i)
        
        


    indexes = [i for i, x in enumerate(v) if x[1]-1 in current]

    
    u=[]
    for i in indexes:
        new=v[i][0]-1

        u.append(v[i])


        
        if a[new] > a[v[i][1]-1]:
            m[new]=m[v[i][1]-1]+1
            current.append(new)
           

            
        else:
            m[new]=m[v[i][1]-1]
            current.append(new)

            
            
    for i in u:
        
        v.remove(i)
        
for i in range(N):
    print(m[i])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]
    dp2 = [0] * (N+1)
    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1

        if parent == None:
            dp[node].append(A[node])
            dp2[node] = 1
        else:
            dp[node] = dp[parent][:]
            dp2[node] = dp2[parent]
            a = A[node]
            for i, val in enumerate(dp[node][1:], 1):
                if val > a:
                    if val == float('inf'):
                        dp2[node] += 1
                    dp[node][i] = a
                    break
            if dp[node][-1] < a:
                dp[node].append(a)
                dp2[node] += 1
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)

    for i in range(1, N+1):
        print(dp2[i])


if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]
    dp2 = [0] * (N+1)
    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1

        if parent == None:
            dp[node].append(A[node])
            dp2[node] = 1
        else:
            for val in dp[parent][1:]:
                dp[node] = dp[parent][:]
                dp2[node] = dp2[parent]
            for i, val in enumerate(dp[node][1:], 1):
                if val > A[node]:
                    if val == float('inf'):
                        dp2[node] += 1
                    dp[node][i] = A[node]
                    break
            if dp[node][-1] < A[node]:
                dp[node].append(A[node])
                dp2[node] += 1
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)

    for i in range(1, N+1):
        print(dp2[i])


if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline
sys.setrecursionlimit(10**7)
def run():
    N = int(input())
    A = [0] + list(map(int, sysread().split()))
    to = [[] for _ in range(N+1)]
    for _ in range(N-1):
        u,v = map(int, sysread().split())
        to[u].append(v)
        to[v].append(u)
    seen = [False] * (N+1)
    stack = [1]
    tree_score = [-1] * (N+1)
    dp = [[float('inf')] for _ in range(N+1)]

    def dfs(node, length=0, parent=None):
        seen[node] = True
        stack.append(node)
        length += 1

        if parent == None:
            dp[node].append(A[node])
        else:
            for val in dp[parent][1:]:
                dp[node].append(val)
            for i, val in enumerate(dp[node][1:], 1):
                if val > A[node]:
                    dp[node][i] = A[node]
                    break
            if dp[node][-1] < A[node]:
                dp[node].append(A[node])
            else:
                dp[node].append(float('inf'))

        for next in to[node]:
            if not seen[next]:
                dfs(next, length, node)

    dfs(1)

    for i in range(1, N+1):
        try:
            s = dp[i][1:].index(float('inf'))
            print(s)
        except:
            print(len(dp[i][1:]))


if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 9] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = 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 = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 18] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    global dp, ans1, ans2
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
aa = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

dp = [10 ** 18] * (n + 10)
dp[0] = 0
ans1 = [0] * n
ans2 = [0] * n


def dfs(i=0, r=-1):
    mi = 0
    ma = n
    while mi != ma:
        mm = (mi + ma) // 2
        if dp[mm] >= aa[i]:
            ma = mm
        else:
            mi = mm + 1

    be = dp[mi]
    dp[mi] = min(dp[mi], aa[i])
    ans1[i] = mi
    ans2[i] = max(ans1[i], ans2[r])

    for j in e[i]:
        if j == r:
            continue
        dfs(j, i)

    dp[mi] = be


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

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


root = Tree(0)
# root.dp([], [])

# equivalent to
current = []
diffs = []
self = root
v = bisect.bisect_left(current, self.val)
stack = [(True, root)]
while stack:
    is_start, self = stack.pop()
    if is_start:
        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:
            stack.append((False, child_tree))
            stack.append((True, child_tree))

            # diffs = child_tree.dp(current, diffs)
    else:
        index, val = diffs.pop()
        if val == -1:
            current.pop()
        else:
            current[index] = val

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


n = int(input())
aa = {}
for j,i in enumerate(map(int,input().split())):
    if i in aa:
        aa[i].append(j)
    else:
        aa[i] = [j]
a = [0] * n
for k,i in enumerate(sorted(list(aa))):
    for j in aa[i]:
        a[j] = 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, i=0, ll=0, rr=-1):
        if rr == -1:
            rr = self.n
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1, ll, (ll+rr)//2),
                             self.get_segment(l, r, i * 2 + 2, (ll+rr)//2, rr))


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)+2), 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 bisect
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

n = int(input())
A = list(map(int, input().split()))
edges = [[]for _ in range(n)]
for _ in range(n-1):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    edges[u].append(v)
    edges[v].append(u)
INF = 10**18
ans = [INF]*n


def dfs(v, parent, lis):
    x = bisect.bisect_left(lis, A[v])
    lis[x] = A[v]
    ans[v] = bisect.bisect_left(lis, INF)
    for v2 in edges[v]:
        if v2 == parent:
            continue
        dfs(v2, v, lis.copy())


dfs(0, -1, [INF]*n)
for x in ans:
    print(x)