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:
def old_combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    w_set = set([_[0] for _ in s1])
    w_set = w_set.union([_[0] for _ in s2])
    w_set = list(w_set)
    w_set.sort()
    i1 = 0
    i2 = 0
    ret = []
    for w in w_set:
        while i1 + 1 < len(s1) and s1[i1 + 1][0] <= w:
            i1 += 1
        while i2 + 1 < len(s2) and s2[i2 + 1][0] <= w:
            i2 += 1
        if s1[i1][1] >= s2[i2][1]:
            val = s1[i1][1]
            com = s1[i1][2]
        else:
            val = s2[i2][1]
            com = s2[i2][2]
        if len(ret) >= 1 and ret[-1][1] >= val:
            continue
        ret.append((w, val, com))
    return ret

def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    len_s1 = len(s1)
    len_s2 = len(s2)
    i1 = 0
    i2 = 0
    ret = []
    while i1 < len_s1 and i2 < len_s2:
        if ret:
            while s1[i1][1] <= ret[-1][1]:
                i1 += 1
                if i1 == len_s1:
                    break
            while s2[i2][1] <= ret[-1][1]:
                i2 += 1
                if i2 == len_s2:
                    break
        if s1[i1][0] < s2[i2][0]:
            ret.append(s1[i1])
            i1 += 1
        elif s1[i1][0] > s2[i2][0]:
            ret.append(s2[i2])
            i2 += 1
        else: # s1[i1][0] == s2[i2][0]
            if s1[i1][1] >= s2[i2][1]:
                ret.append(s1[i1])
            else:
                ret.append(s2[i2])
            i1 += 1
            i2 += 1
    while i1 < len_s1:
        if ret:
            if s1[i1][1] > ret[-1][1]:
                ret.append(s1[i1])
        else:
            ret.append(s1[i1])
        i1 += 1
    while i2 < len_s2:
        if ret:
            if s2[i2][1] > ret[-1][1]:
                ret.append(s2[i2])
        else:
            ret.append(s2[i2])
        i2 += 1
    return ret


N = int(input())
A = [int(_) for _ in input().split()]

#print('hoge1')
connection = [[] for _ in range(N + 1)]
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    connection[u].append(v)
    connection[v].append(u)

#print('hoge2')
parent = [None] * (N + 1)
parent[0] = 0
parent[1] = 0
ret = [None] * (N + 1)
ret[0] = [(0, 0, None)]
stack = [1]
while stack:
    i = stack.pop()
    for v in connection[i]:
        if ret[v] is not None:
            continue
        parent[v] = i
        stack.append(v)
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    #print(ret[i])
    #print(ret[i][-1][1])

#print(ret)
for i in range(1, N + 1):
    print(ret[i][-1][1])
#print('ok')

Submission status: Time Limit Exceeded

Solution code:
def old_combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    w_set = set([_[0] for _ in s1])
    w_set = w_set.union([_[0] for _ in s2])
    w_set = list(w_set)
    w_set.sort()
    i1 = 0
    i2 = 0
    ret = []
    for w in w_set:
        while i1 + 1 < len(s1) and s1[i1 + 1][0] <= w:
            i1 += 1
        while i2 + 1 < len(s2) and s2[i2 + 1][0] <= w:
            i2 += 1
        if s1[i1][1] >= s2[i2][1]:
            val = s1[i1][1]
            com = s1[i1][2]
        else:
            val = s2[i2][1]
            com = s2[i2][2]
        if len(ret) >= 1 and ret[-1][1] >= val:
            continue
        ret.append((w, val, com))
    return ret

def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    len_s1 = len(s1)
    len_s2 = len(s2)
    i1 = 0
    i2 = 0
    ret = []
    while i1 < len_s1 and i2 < len_s2:
        if ret:
            while s1[i1][1] <= ret[-1][1]:
                i1 += 1
                if i1 == len_s1:
                    break
            while s2[i2][1] <= ret[-1][1]:
                i2 += 1
                if i2 == len_s2:
                    break
        if s1[i1][0] < s2[i2][0]:
            ret.append(s1[i1])
            i1 += 1
        elif s1[i1][0] > s2[i2][0]:
            ret.append(s2[i2])
            i2 += 1
        else: # s1[i1][0] == s2[i2][0]
            if s1[i1][1] >= s2[i2][1]:
                ret.append(s1[i1])
            else:
                ret.append(s2[i2])
            i1 += 1
            i2 += 1
    while i1 < len_s1:
        if ret:
            if s1[i1][1] > ret[-1][1]:
                ret.append(s1[i1])
        else:
            ret.append(s1[i1])
        i1 += 1
    while i2 < len_s2:
        if ret:
            if s2[i2][1] > ret[-1][1]:
                ret.append(s2[i2])
        else:
            ret.append(s2[i2])
        i2 += 1
    return ret



N = int(input())
A = [int(_) for _ in input().split()]

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

parent = [None] * (N + 1)
child = [[] for _ in range(N + 1)]
stack = [1]
parent[0] = 0
parent[1] = 0
while stack:
    u = stack.pop()
    for v in connection[u]:
        if parent[v] is not None:
            continue
        parent[v] = u
        child[u].append(v)
        stack.append(v)

ret = [(0, 0, None)] * (N + 1)
ret[0] = [(0, 0, None)]
stack = [1]
while stack:
    i = stack.pop()
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    stack += child[i]
    #print(ret[i])
    #print(ret[i][-1][1])

#print(ret)
for i in range(1, N + 1):
    print(ret[i][-1][1])
#print('ok')

Submission status: Time Limit Exceeded

Solution code:
def combine(s1, s2):
    '''
    combine two scores
    s1, s2: [(last_v, cnt, comment), ...]
    return: same format
    '''
    w_set = set([_[0] for _ in s1])
    w_set = w_set.union([_[0] for _ in s2])
    w_set = list(w_set)
    w_set.sort()
    i1 = 0
    i2 = 0
    ret = []
    for w in w_set:
        while i1 + 1 < len(s1) and s1[i1 + 1][0] <= w:
            i1 += 1
        while i2 + 1 < len(s2) and s2[i2 + 1][0] <= w:
            i2 += 1
        if s1[i1][1] >= s2[i2][1]:
            val = s1[i1][1]
            com = s1[i1][2]
        else:
            val = s2[i2][1]
            com = s2[i2][2]
        if len(ret) >= 1 and ret[-1][1] >= val:
            continue
        ret.append((w, val, com))
    return ret



N = int(input())
A = [int(_) for _ in input().split()]

connection = [[] for _ in range(N + 1)]
for n in range(N - 1):
    u, v = (int(_) for _ in input().split())
    connection[u].append(v)
    connection[v].append(u)
parent = [None] * (N + 1)
child = [[] for _ in range(N + 1)]
stack = [1]
parent[0] = 0
parent[1] = 0
while stack:
    u = stack.pop()
    for v in connection[u]:
        if parent[v] is not None:
            continue
        parent[v] = u
        child[u].append(v)
        stack.append(v)

ret = [(0, 0, None)] * (N + 1)
ret[0] = [(0, 0, None)]
stack = [1]
while stack:
    i = stack.pop()
    #print('== {:} =='.format(i))
    score = ret[parent[i]]
    value = 1
    for _ in score:
        if _[0] >= A[i - 1]:
            break
        value = max(value, _[1] + 1)
    score_ = [(0, 0, None), (A[i - 1], value, None)]
    #print(score)
    #print(score_)
    ret[i] = combine(score, score_)
    stack += child[i]
    #print(ret[i])
    #print(ret[i][-1][1])

#print(ret)

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

Submission status: Time Limit Exceeded

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


def main() -> None:
    N = ri()
    A = rmi()
    U, V = [], []
    for n in range(N - 1):
        u, v = rmi()
        U.append(u)
        V.append(v)
    tree = {}
    for n in range(N):
        tree[n] = []
    for u, v in zip(U, V):
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)
    routes = dfs(tree)
    for k in range(N):
        A_on_route = list(map(lambda r: A[r], routes[k]))
        w(lis(A_on_route))


def dfs(tree):
    import copy
    import queue
    q = queue.Queue()
    result = {}
    result[0] = [0]
    for cand in tree[0]:
        q.put([0, cand])
    while not q.empty():
        route = q.get()
        if route[-1] in result:
            continue
        result[route[-1]] = route
        for new_cand in tree[route[-1]]:
            if new_cand in result:
                continue
            new_route = copy.copy(route)
            new_route.append(new_cand)
            q.put(new_route)
    return result


def lis(l):
    # https://qiita.com/python_walker/items/d1e2be789f6e7a0851e5
    import bisect
    LIS = [l[0]]
    for i in range(len(l)):
        if LIS[-1] < l[i]:
            LIS.append(l[i])
        else:
            LIS[bisect.bisect_left(LIS, l[i])] = l[i]
    return(len(LIS))


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**9)
    main()

Submission status: Time Limit Exceeded

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


def main() -> None:
    N = ri()
    A = rmi()
    U, V = [], []
    for n in range(N - 1):
        u, v = rmi()
        U.append(u)
        V.append(v)
    tree = {}
    for n in range(N):
        tree[n] = []
    for u, v in zip(U, V):
        tree[u - 1].append(v - 1)
        tree[v - 1].append(u - 1)
    routes = dfs(tree)
    for k in range(N):
        A_on_route = list(map(lambda r: A[r], routes[k]))
        w(lis(A_on_route))


def dfs(tree):
    import copy
    import queue
    q = queue.Queue()
    result = {}
    result[0] = [0]
    for cand in tree[0]:
        q.put([0, cand])
    while not q.empty():
        route = q.get()
        if route[-1] in result:
            continue
        result[route[-1]] = route
        for new_cand in tree[route[-1]]:
            new_route = copy.copy(route)
            new_route.append(new_cand)
            q.put(new_route)
    return result


def lis(l):
    import bisect
    LIS = [l[0]]
    for i in range(len(l)):
        if LIS[-1] < l[i]:
            LIS.append(l[i])
        else:
            LIS[bisect.bisect_left(LIS, l[i])] = l[i]
    return(len(LIS))


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> tuple:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(*data, delim: str = ' ') -> None:
    print(delim.join(map(str, data)))


if __name__ == '__main__':
    import sys
    sys.setrecursionlimit(10**9)
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
from copy import copy, deepcopy
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            lis = copy(LIS)
            if A[u] > lis[-1]:
                lis.append(A[u])
            else:
                ind = bisect_left(LIS,A[u])
                lis[ind] = A[u]
            ans[u] = len(lis)
            dfs(u,lis)
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import copy, deepcopy
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


ans = [0]*N
visited = [False]*N
visited[0]=True
ans[0] = 1
vs = deque([0])
LISs = deque([[A[0]]])
while len(vs)>0:
    v = vs.popleft()
    LIS = LISs.popleft()
    for u in edge[v]:
        if visited[u]==False:
            visited[u] = True
            lis = copy(LIS)
            if A[u]>lis[-1]:
                lis.append(A[u])
            else:
                ind = bisect_left(lis,A[u])
                lis[ind] = A[u]
            ans[u] = len(lis)
            vs.append(u)
            LISs.append(lis)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import copy, deepcopy
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


ans = [0]*N
visited = [False]*N
visited[0]=True
ans[0] = 1
vs = deque([0])
LISs = deque([[A[0]]])
while len(vs)>0:
    v = vs.popleft()
    LIS = LISs.popleft()
    for u in edge[v]:
        if visited[u]==False:
            visited[u] = True
            lis = copy(LIS)
            ind = bisect_left(lis,A[u])
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            vs.append(u)
            LISs.append(lis)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import copy, deepcopy
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


ans = [0]*N
visited = [False]*N
visited[0]=True
ans[0] = 1
d = deque([(0,[A[0]])])
while len(d)>0:
    v,LIS = d.popleft()
    for u in edge[v]:
        if visited[u]==False:
            visited[u] = True
            lis = copy(LIS)
            ind = bisect_left(lis,A[u])
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            d.append((u,lis))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
from copy import copy, deepcopy
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            ind = bisect_left(LIS,A[u])
            lis = copy(LIS)
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            dfs(u,lis)
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from copy import copy, deepcopy
from bisect import bisect_left, bisect_right
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)


ans = [0]*N
visited = [False]*N
visited[0]=True
ans[0] = 1
d = deque([[0,[A[0]]]])
while len(d)>0:
    v,LIS = d.popleft()
    for u in edge[v]:
        if visited[u]==False:
            visited[u] = True
            lis = copy(LIS)
            ind = bisect_left(lis,A[u])
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            d.append([u,lis])
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left, bisect_right
from copy import copy, deepcopy
N = int(input())
A = list(map(int, input().split()))
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(v,LIS):
    if len(edge[v])==0:
        return
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            ind = bisect_left(LIS,A[u])
            lis = copy(LIS)
            if ind < len(lis):
                lis[ind] = A[u]
            else:
                lis.append(A[u])
            ans[u] = len(lis)
            dfs(u,lis)
    return

ans = [0]*N
visited = [False]*N
visited[0]=True
LIS = [A[0]]
ans[0] = 1
dfs(0,LIS)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
import time

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n = int(input())
    a = list(map(int, readline().split()))

    import networkx as nx
    G = nx.Graph()

    for _ in range(n - 1):
        u, v = map(int, readline().split())
        u, v = u - 1, v - 1
        G.add_edge(u, v)

    ans = [0] * n
    dp = [INF] * n
    dp[0] = a[0]

    from collections import deque, namedtuple
    import bisect

    stack = deque()
    Params = namedtuple("Params", ["node", "dp_index", "prev_value", "new_value"])
    par = 0
    stack.append(Params(0, 0, INF, a[0]))

    for prev, cur in nx.algorithms.edge_dfs(G, source=0):
        if par != prev:
            while stack:
                params = stack.pop()
                if params.node == prev:
                    stack.append(params)
                    break
                ans[params.node] = bisect.bisect_left(dp, INF)
                dp[params.dp_index] = params.prev_value
        new_val = a[cur]
        index = bisect.bisect_left(dp, new_val)
        prev_val = dp[index]
        dp[index] = new_val
        stack.append(Params(cur, index, prev_val, new_val))
        par = cur

    while stack:
        params = stack.pop()
        ans[params.node] = bisect.bisect_left(dp, INF)
        dp[params.dp_index] = params.prev_value

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

INF = 10**10

N = int(input())
a = list(map(int,input().split()))
T = [set() for x in range(N)]
for i in range(N-1):
    u,v = map(int,input().split())
    u -= 1
    v -= 1
    T[u].add(v)
    T[v].add(u)

search = [0]*N

A = [INF]*N

ans = [-1]*N

def dfs(V,i):
    num = a[V]
    k = bisect.bisect_left(A,num)
    v = A[k]
    A[k] = num
    if v == INF:
        i += 1
    ans[V] = i
    for VV in T[V]:
        if search[VV]:
            continue
        search[VV] = 1
        dfs(VV,i)
    A[k] = v

search[0] = 1
dfs(0,0)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def S(): return sys.stdin.readline().rstrip()
def LS(): return sys.stdin.readline().split()
def LS2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**5+10)
#input = sys.stdin.readline
from bisect import bisect_left

def dfs(i,before):
    global seq
    global ans
    added  = 0

    #現在地のAの値を、以前までのseqリストのどこに追加するか決める
    pos = bisect_left(seq,a[i-1])
    if len(seq)<= pos:
        seq.append(a[i-1])
        added  = 1
    else:
        old = seq[pos]
        seq[pos]=a[i-1]
    ans[i-1]=len(seq)

    #隣接する頂点に関して再帰
    for u in to[i]:
        if u==before:
            continue
        dfs(u,i)

    #seq配列をもとに戻す
    if added==1:
        seq=seq[:-1]
    else:
        seq[pos]=old


N = I()
a = LI()
to = [[] for i in range(N+1)]
to[0] += [1]
for i in range(N-1):
    u,v = MI()
    to[u].append(v)
    to[v].append(u)
seq = []
ans = [-1]*(N)

dfs(1,-1)
[print(i) for i in ans]

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))

result = [-1 for _ in range(n)]
tree = [[] for _ in range(n)]
for _i in range(n-1):
    u, v = map(int, input().split())
    u, v = u-1, v-1
    tree[u].append(v)
    tree[v].append(u)
INF = float('inf')
dp = [INF for _i in range(n+1)]


def dfs(p, d, x):
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = bisect_left(d, INF)
    for j in tree[p]:
        if j != x:
            dfs(j, d.copy(), p)

dfs(0, dp, -1)

for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right
n = int(input())
a = list(map(int, input().split()))

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

dp = [float('inf') for _i in range(n+1)]
q = [[0, dp]]
q = deque(q)
while q:
    p, d = q.popleft()
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = bisect_left(d, float("inf")-1)
    for i in tree[p]:
        if result[i] < 0:
            q.appendleft([i, d.copy()])

for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from bisect import bisect_left, bisect_right
from copy import deepcopy
n = int(input())
a = list(map(int, input().split()))

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

dp = [float('inf') for _i in range(n+1)]
q = [[0, dp]]
q = deque(q)
while q:
    p, d = q.popleft()
    i = bisect_left(d, a[p])
    d[i] = a[p]
    result[p] = bisect_left(d, float("inf")-1)
    for i in tree[p]:
        if result[i] < 0:
            q.append([i, deepcopy(d)])

for i in result:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, copy
from collections import deque
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
def main():
    n = int(input())
    a = list(map(int,input().split()))
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        p,q = map(int,input().split())
        p -= 1
        q -= 1
        g[p].append(q)
        g[q].append(p)
    dis = [10**10]*n
    dis[0] = 0
    que = deque()
    que.append(0)
    pr = [0 for _ in range(n)]
    pr[0] = 1
    ans = ['' for _ in range(n)]
    ans[0] = [a[0]]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] <= dis[go] + 1:
                continue
            lis = [0 for _ in range(len(ans[go]))]
            for j in range(len(ans[go])):
                lis[j] = ans[go][j]
            if a[g[go][i]] > lis[-1]:
                lis.append(a[g[go][i]])
            else:
                lis[bisect.bisect_left(lis,a[g[go][i]])] = a[g[go][i]]
            ans[g[go][i]] = lis
            dis[g[go][i]] = dis[go] + 1
            que.append(g[go][i])
    for i in range(n):
        print(len(ans[i]))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
INF = float("inf")


from collections import defaultdict


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, a: "List[int]", u: "List[int]", v: "List[int]"):

    g = Graph(N)
    for x, y in zip(u, v):
        g.add_edge(x-1, y-1)

    ans = [0]*N

    dp = [INF]*N
    event = []
    var = {"last": 0}

    def dfs(curr, par):
        i = bisect_left(dp, a[curr])
        if dp[i] > a[curr]:
            if dp[i] == INF:
                var["last"] = i
            event.append((curr, i, dp[i]))
            dp[i] = a[curr]

        ans[curr] = len(dp[:var["last"]+1])

        for child, w in g.E[curr]:
            if child == par:
                continue
            dfs(child, curr)

        c, i, v = event[-1]
        if c == curr:
            dp[i] = v
            if v == INF:
                var["last"] = i-1
            event.pop()

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

    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: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
#from itertools import combinations
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)
    dp = [float('inf')] * (N+2)
    dp[0] = -float('inf')
    ddp2 = [0]
    paths = []
    actions = []# (idx, pre, pro)
    ans = [0] * (N+1)
    def dfs(node, parent=None):

        a = A[node]
        seen[node] = True
        if parent == None:
            paths.append(node)
            actions.append((1, dp[1], a, 1))
            dp[1] = a
            ddp2[0] += 1
        else:
            paths.append(node)
            idx = bin_search(dp[:len(paths)+1], a)
            if idx == float('inf'):
                actions.append((len(paths), float('inf'), a, 1))
                dp[len(paths)] = a
                ddp2[0] += 1
            else:
                if dp[idx] == float('inf'):
                    actions.append((idx, dp[idx], a, 1))
                    ddp2[0] += 1
                else:
                    actions.append((idx, dp[idx], a, 0))
                dp[idx] = a
        ans[node] = ddp2[0]
        for next in to[node]:
            if not seen[next]:
                dfs(next, node)

        idx, pre, pro, change = actions.pop()
        paths.pop()
        dp[idx] = pre
        ddp2[0] -= change

    dfs(1)
    for s in ans[1:]:
        print(s)
    return None

def bin_search(A, x):
    '''
    return index which is lowest in values more than or equal to x
    '''
    low = 0
    high = len(A) - 1
    c = (low + high) // 2
    if A[-1] < x: return float('inf')
    while high - low > 1:
        if A[c] < x:
            low = c
            c = (low + high) // 2

        elif A[c] > x:
            high = c
            c = (high + low) // 2
        else:
            return c
    return high

if __name__ == "__main__":
    run()