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=list(map(int,input().split()))
g = [[]for _ in range(n)]
for i in range(n-1):
    u,v=map(int,input().split())
    g[u-1].append(v-1)
    g[v-1].append(u-1)
import copy
import queue
import bisect
check = [False]*n
check[0] = True
li = [a[0]]
q= queue.Queue()
q.put([0,li])
ans = [0]*n
ans[0] = 1
while not q.empty():
    now,lisOrigin= q.get()
    for ne in g[now]:
        if check[ne]:
            continue
        check[ne] = True
        lis = copy.deepcopy(lisOrigin)
        if a[ne] > lis[-1]:
            lis.append(a[ne])
        else:
            lis[bisect.bisect_left(lis,a[ne])] = a[ne]
        q.put([ne,lis])
        ans[ne] = len(lis)

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

Submission status: Time Limit Exceeded

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


def inp():
    return int(input())


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


def dfs(s, b, lis, ansl, lines, aa):
    a = aa[s]
    idx = bisect.bisect_left(lis, a)

    if len(lis) == idx:
        lis.append(a)
    else:
        lis[idx] = a

    ansl[s] = len(lis)

    if len(lines[s]) >= 3:
        for t in lines[s]:
            if t != b:
                dfs(t, s, lis.copy(), ansl, lines, aa)
    else:
        for t in lines[s]:
            if t != b:
                dfs(t, s, lis, ansl, lines, aa)


def main():
    N = inp()
    aa = inpl()

    lines = [[] for _ in range(N)]
    for _ in range(N - 1):
        s, t = inpl()
        s -= 1
        t -= 1
        lines[s].append(t)
        lines[t].append(s)

    lines[0].append(-1)

    ansl = [0] * N

    dfs(0, -1, [], ansl, lines, aa)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def EulerTour(n, X, i0):
    def bl(k):
        l, r = -1, n
        while r - l > 1:
            m = (l + r) // 2
            if L[m][-1] < k:
                l = m
            else:
                r = m
        return l + 1

    inf = 1 << 30
    P = [-1] * n
    Q = [~i0, i0]
    ANS = [0] * n
    L = [[inf] for _ in range(n)]
    I = [0] * n
    while Q:
        i = Q.pop()
        if i < 0:
            i = ~i
            L[I[i]].pop()
            continue
        if i >= 0:
            k = A[i]
            b = bl(k)
            L[b].append(k)
            I[i] = b
            ANS[i] = bl(inf)
        for a in X[i][::-1]:
            if a != P[i]:
                P[a] = i
                for k in range(len(X[a])):
                    if X[a][k] == i:
                        del X[a][k]
                        break
                Q.append(~a)
                Q.append(a)
    return ANS

print("\n".join(map(str, EulerTour(N, X, 0))))

Submission status: Time Limit Exceeded

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


def inp():
    return int(input())


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


def main():
    def dfs(s, b, lis, ansl):

        a = aa[s]
        idx = bisect.bisect_left(lis, a)

        if len(lis) == idx:
            lis.append(a)
        else:
            lis[idx] = a

        ansl[s] = len(lis)

        if len(lines[s]) >= 3:
            for t in lines[s]:
                if t != b:
                    dfs(t, s, lis.copy(), ansl)
        else:
            for t in lines[s]:
                if t != b:
                    dfs(t, s, lis, ansl)
    N = inp()
    aa = inpl()

    lines = [[] for _ in range(N)]
    for _ in range(N - 1):
        s, t = inpl()
        s -= 1
        t -= 1
        lines[s].append(t)
        lines[t].append(s)

    lines[0].append(-1)

    ansl = [0] * N

    dfs(0, -1, [], ansl)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
from bisect import bisect_left as bisect
input = sys.stdin.readline
sys.setrecursionlimit(2 * 10**6)


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


def main():
    N = int(input())
    A = inpl()
    edges = [[] for _ in range(N + 1)]
    for _ in range(N - 1):
        u, v = inpl()
        edges[u].append(v)
        edges[v].append(u)
    DPs = [[]] * (N + 1)

    Q = deque()
    Q.append(1)
    parent = [-1] * (N + 1)
    parent[1] = 0
    while Q:
        nv = Q.popleft()
        DPs[nv] = DPs[parent[nv]].copy()
        t = bisect(DPs[nv], A[nv - 1])
        if t >= len(DPs[nv]):
            DPs[nv].append(A[nv - 1])
        else:
            DPs[nv][t] = A[nv - 1]

        for kouho in edges[nv]:
            if parent[kouho] == -1:
                Q.append(kouho)
                parent[kouho] = nv

    for i in range(1, N + 1):
        print(len(DPs[i]))
    # print(edges)
    # print(parent)
    # print(DPs)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], True)]
    while len(q):
        cur, prev, lis, override = q.pop()
        idx = bisect_left(lis, A[cur])
        if override:
            if idx == len(lis):
                lis.append(A[cur])
            else:
                lis[idx] = A[cur]
            nxt_lis = lis
        else:
            nxt_lis = lis[:idx] + [A[cur]] + lis[idx+1:]
        ans[cur] = len(nxt_lis)
        nxt_override = (cur != 0)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis, nxt_override))
            nxt_override = False
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque
import copy
def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)
n = int(input())
a = tuple(map(int, input().split()))
G = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)

letu = [[] for _ in range(n+1)]
letu[1].append(1)
que = deque([1])

while que:
    q = que.popleft()

    for nq in G[q]:
        let = copy.deepcopy(letu[q])
        if letu[nq] != []: #seen配列としても使う。seenないと閉路でWA
            continue
        letu[nq].extend(let+[nq])
        que.append(nq)
for j in range(1,n+1):
    tmp = []
    for aa in letu[j]:
        tmp.append(a[aa-1])
    print(lis(tmp))

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N = int(readline())
    a = tuple(map(int, readline().split()))
    uv = map(int, read().split())
    graph = [[] for _ in range(N)]
    for u, v in zip(uv, uv):
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    answer = [-1] * N
    stack = [(0, [a[0]])]
    answer[0] = 1

    while stack:
        V, LIS = stack.pop()
        if V == 0:
            for v in graph[V]:
                if answer[v] != -1:
                    continue
                if a[v] > LIS[-1]:
                    new_LIS = LIS[:] + [a[v]]

                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, a[v])] = a[v]
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
            continue
        if len(graph[V]) > 2:
            for v in graph[V]:
                if answer[v] != -1:
                    continue
                if a[v] > LIS[-1]:
                    new_LIS = LIS[:] + [a[v]]

                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, a[v])] = a[v]
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
        else:
            for v in graph[V]:
                if answer[v] != -1:
                    continue
                if a[v] > LIS[-1]:
                    LIS += [a[v]]
                else:
                    LIS[bisect_left(LIS, a[v])] = a[v]
                answer[v] = len(LIS)
                stack.append((v, LIS))

    print('\n'.join(map(str, answer)))


if __name__ == '__main__':
    main()

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)
    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 = copy.copy(ans[go])
            
            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:
mod = 1000000007
eps = 10**-9


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

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

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    dp = [[A[0]]]
    ID = [0] * (N+1)
    ans = [0] * (N+1)
    ans[1] = 1
    while que:
        v = que.popleft()
        flg = 1
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)
                if flg:
                    uu = u
                    flg = 0
                    continue
                a = A[u-1]
                ID[u] = len(dp)
                dp.append(dp[ID[v]][:])
                j = bisect_left(dp[-1], a)
                if j == len(dp[-1]):
                    dp[-1].append(a)
                    ans[u] = len(dp[-1])
                else:
                    dp[-1][j] = a
                    ans[u] = len(dp[-1])
        if flg == 0:
            a = A[uu-1]
            ID[uu] = ID[v]
            j = bisect_left(dp[ID[uu]], a)
            if j == len(dp[ID[uu]]):
                dp[ID[uu]].append(a)
            else:
                dp[ID[uu]][j] = a
            ans[uu] = len(dp[ID[uu]])

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


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


dp = [None for _ in range(N)]


dp[0] = [a[0]]
Q = [0]

while Q:
    u = Q.pop()
    for v in to[u]:
        if dp[v] is not None:
            continue
        dp[v] = dp[u][::]
        if a[v] > dp[u][-1]:
            dp[v].append(a[v])
        else:
            dp[v][bisect.bisect_left(dp[v], a[v])] = a[v]
        Q.append(v)

for d in dp:
    print(len(d))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [], True)]
    while len(q):
        cur, prev, lis, override = q.pop()
        idx = bisect_left(lis, A[cur])
        if override:
            if idx == len(lis):
                lis.append(A[cur])
            else:
                lis[idx] = A[cur]
            nxt_lis = lis
        else:
            nxt_lis = lis[:idx] + [A[cur]] + lis[idx+1:]
        ans[cur] = len(nxt_lis)
        nxt_override = len(adj[cur]) <= 2 and cur != 0
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis, nxt_override))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
input = sys.stdin.readline


def inp():
    return int(input())


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


N = inp()

aa = inpl()
lines = [set() for _ in range(N)]
for _ in range(N - 1):
    s, t = inpl()
    s -= 1
    t -= 1
    lines[s].add(t)
    lines[t].add(s)

lines[0].add(-1)


ansl = [0] * N


def dfs(s, b, lis):
    global ansl

    a = aa[s]
    idx = bisect.bisect_left(lis, a)

    if len(lis) == idx:
        lis.append(a)
    else:
        lis[idx] = a

    ansl[s] = len(lis)

    if len(lines[s]) >= 3:
        for t in lines[s]:
            if t != b:
                dfs(t, s, lis.copy())
    else:
        for t in lines[s]:
            if t != b:
                dfs(t, s, lis)


dfs(0, -1, [])


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N = int(readline())
    a = tuple(map(int, readline().split()))
    uv = map(int, read().split())
    graph = [[] for _ in range(N)]
    for u, v in zip(uv, uv):
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    answer = [-1] * N
    stack = [(0, [a[0]])]
    answer[0] = 1

    while stack:
        V, LIS = stack.pop()
        if len(graph[V]) > 1:
            for v in graph[V]:
                if answer[v] != -1:
                    continue
                if a[v] > LIS[-1]:
                    new_LIS = LIS[:] + [a[v]]

                else:
                    new_LIS = LIS[:]
                    new_LIS[bisect_left(new_LIS, a[v])] = a[v]
                answer[v] = len(new_LIS)
                stack.append((v, new_LIS))
        else:
            v = graph[V][0]
            if answer[v] != -1:
                continue
            if a[v] > LIS[-1]:
                LIS += [a[v]]
            else:
                LIS[bisect_left(LIS, a[v])] = a[v]
            answer[v] = len(LIS)
            stack.append((v, LIS))

    print('\n'.join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from collections import deque
import copy
def lis(A: list):
    L = [A[0]]
    for a in A[1:]:
        if a > L[-1]:
            # Lの末尾よりaが大きければ増加部分列を延長できる
            L.append(a)
        else:
            # そうでなければ、「aより小さい最大要素の次」をaにする
            # 該当位置は、二分探索で特定できる
            L[bisect_left(L, a)] = a
    return len(L)
n = int(input())
a = list(map(int, input().split()))
G = [[] for _ in range(n+1)]
for i in range(n-1):
    u,v = map(int, input().split())
    G[u].append(v)
    G[v].append(u)
dist = [-1]*(n+1)
dist[1] = 0
letu = [[] for _ in range(n+1)]
letu[1].append(1)
que = deque([1])

while que:
    q = que.popleft()
    d = dist[q]#先に何度も使うものはdと書いておく。計算量下げ

    for nq in G[q]:
        let = copy.deepcopy(letu[q])
        if dist[nq] != -1: #seen配列としても使う。seenないと閉路でWA
            continue
        dist[nq] = d + 1
        let.extend([nq])
        letu[nq].extend(let)
        que.append(nq)
for j in range(1,n+1):
    tmp = []
    for aa in letu[j]:
        tmp.append(a[aa-1])
    print(lis(tmp))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
sys.setrecursionlimit(10 ** 7)
def solve(G, a, lis, pre, p, ans):
    lis2 = np.copy(lis)
    idx = np.searchsorted(lis2, a[p], side="left")
    lis2[idx] = a[p]
    ans[p] = np.searchsorted(lis2, np.inf, side="left")
    for v in G[p]:
        if v == pre:
            continue
        solve(G, a, lis2, p, v, ans)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    G = [[] for _ in range(n)]
    for _ in range(n-1):
        u, v = map(int, input().split())
        u, v = u-1, v-1
        G[u].append(v)
        G[v].append(u)
    lis = np.full(n+1, np.inf)
    ans = [None]*n
    solve(G, a, lis, -1, 0, ans)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


def main():
    N = int(input())
    A = list(map(int, input().split()))
    adj = [set() for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        adj[u-1].add(v-1)
        adj[v-1].add(u-1)
    ans = [0] * N
    q = [(0, -1, [])]
    while len(q):
        cur, prev, lis = q.pop()
        idx = bisect_left(lis, A[cur])
        nxt_lis = lis[:idx] + [A[cur]] + lis[idx+1:]
        ans[cur] = len(nxt_lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, nxt_lis))
    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

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N = int(readline())
    a = tuple(map(int, readline().split()))
    uv = map(int, read().split())
    graph = [[] for _ in range(N)]
    for u, v in zip(uv, uv):
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    answer = [-1] * N
    stack = [(0, [a[0]])]
    answer[0] = 1

    while stack:
        V, LIS = stack.pop()
        for v in graph[V]:
            if answer[v] != -1:
                continue
            if a[v] > LIS[-1]:
                new_LIS = LIS[:] + [a[v]]

            else:
                new_LIS = LIS[:]
                new_LIS[bisect_left(new_LIS, a[v])] = a[v]
            answer[v] = len(new_LIS)
            stack.append((v, new_LIS))

    print('\n'.join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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



def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [A[t]]
    while prev[t] != s:
        path.append(A[prev[t]])
        prev[t] = prev[prev[t]]
    path.append(A[s])
    path = path[::-1]
    return path

def main():
    cost = [[float("inf") for i in range(N)] for i in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        cost[u][v] = 1
        cost[v][u] = 1

    for i in range(N):
        seq = dijkstra_back(0,i,N,N-1,cost)
        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))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect
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)
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] <= dis[go] + 1:
                continue
            dis[g[go][i]] = dis[go] + 1
            que.append(g[go][i])
    for x in range(n):
        root = [x]
        que = deque()
        que.append(x)
        distance = dis[x]
        while que:
            go = que.pop()
            for i in range(len(g[go])):
                if dis[g[go][i]] == distance - 1:
                    distance -= 1
                    root.append(g[go][i])
                    que.append(g[go][i])
                    break
        f = []
        for i in range(len(root)):
            f.append(a[root[i]])
        f.reverse()
        lis = [f[0]]
        for i in range(len(f)):
            if f[i] > lis[-1]:
                lis.append(f[i])
            else:
                lis[bisect.bisect_left(lis,f[i])] = f[i]
        print(len(lis))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

read = sys.stdin.read
readline = sys.stdin.readline


def main():
    N = int(readline())
    a = tuple(map(int, readline().split()))
    uv = map(int, read().split())
    graph = [[] for _ in range(N)]
    for u, v in zip(uv, uv):
        u -= 1
        v -= 1
        graph[u].append(v)
        graph[v].append(u)

    INF = float('inf')
    answer = [-1] * N
    stack = [(0, [a[0]])]
    answer[0] = 1

    while stack:
        V, LIS = stack.pop()
        for v in graph[V]:
            if answer[v] != -1:
                continue
            if a[v] > LIS[-1]:
                new_LIS = LIS[:] + [a[v]]

            else:
                new_LIS = LIS[:]
                new_LIS[bisect_left(new_LIS, a[v])] = a[v]
            answer[v] = len(new_LIS)
            stack.append((v, new_LIS))

    print('\n'.join(map(str, answer)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
A=[int(i) for i in input().split()]
edge=[[] for i 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)
inf=float("inf")
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)
import bisect
import copy
Ans=[[] for i in range(n)]
for i in range(n):
  v=TS[i]
  if i==0:
    Ans[i].append(A[v])
  else:
    Prev=copy.deepcopy(Ans[Par[v]])
    a=A[v]
    if a>Prev[-1]:
      Prev.append(a)
    else:
      Prev[bisect.bisect_left(Prev,a)]=a
    Ans[v]=Prev
for i in range(n):
  print(len(Ans[i]))

Submission status: Time Limit Exceeded

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


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

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

    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    dp = [[] for _ in range(N+1)]
    dp[1] = [A[0]]
    ans = [0] * (N+1)
    ans[1] = 1
    while que:
        v = que.popleft()
        flg = 1
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                que.append(u)
                if flg:
                    uu = u
                    flg = 0
                    continue
                a = A[u-1]
                j = bisect_left(dp[v], a)
                if j == len(dp[v]):
                    dp[u] = dp[v][:]
                    dp[u].append(a)
                    ans[u] = len(dp[u])
                else:
                    dp[u] = dp[v][:]
                    dp[u][j] = a
                    ans[u] = len(dp[u])
        if flg == 0:
            a = A[uu-1]
            dp[uu] = dp[v]
            j = bisect_left(dp[uu], a)
            if j == len(dp[uu]):
                dp[uu].append(a)
            else:
                dp[uu][j] = a
            ans[uu] = len(dp[uu])

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def LIS(a): #最長増加部分列
    lis = [a[0]]
    for i in range(len(a)):
        if a[i] > lis[-1]:
            lis.append(a[i])
        else:
            lis[bisect.bisect_left(lis,a[i])] = a[i]
    return len(lis)
    
def dijkstra1(s,n,g): # 全辺距離1のグラフ
    dis = [10**10]*n
    dis[s] = 0
    que = deque()
    que.append(s)
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] <= dis[go] + 1:
                continue
            dis[g[go][i]] = dis[go] + 1
            que.append(g[go][i])
    return dis

def dijkstra1_path(x,dis,g):
    root = [x]
    que = deque()
    que.append(x)
    distance = dis[x]
    while que:
        go = que.pop()
        for i in range(len(g[go])):
            if dis[g[go][i]] == distance - 1:
                distance -= 1
                root.append(g[go][i])
                que.append(g[go][i])
                break
    return root

def main():
    n = inp()
    a = inpl()
    g = [[] for _ in range(n)]
    for _ in range(n-1):
        p,q = inpm()
        p -= 1
        q -= 1
        g[p].append(q)
        g[q].append(p)
    dis = dijkstra1(0,n,g)
    for i in range(n):
        root = dijkstra1_path(i,dis,g)
        f = []
        for i in range(len(root)):
            f.append(a[root[i]])
        f.reverse()
        print(LIS(f))
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
FAST_IO = 0
if FAST_IO:
    import io, sys, atexit
    rr = iter(sys.stdin.read().splitlines()).next
    sys.stdout = _OUTPUT_BUFFER = io.BytesIO()
    @atexit.register
    def write():
        sys.__stdout__.write(_OUTPUT_BUFFER.getvalue())
else:
    rr = raw_input
rri = lambda: int(rr())
rrm = lambda: map(int, rr().split())

####
from bisect import bisect_left
def solve(N, A, graph):
    res = [None] * N
    res[0] = [A[0]]

    stack = [[0,-1]]
    while stack:
        node, par = stack.pop()
        x = A[node]
        if par >= 0:
            i = bisect_left(res[par], x)
            res[node] = res[par][:]
            if i >= len(res[node]):
                res[node].append(x)
            else:
                res[node][i] = x
        for nei in graph[node]:
            if nei != par:
                stack.append([nei, node])

    return map(len, res)

N = rri()
A = rrm()
graph = [[] for _ in xrange(N)]
for _ in xrange(N - 1):
    u, v = rrm()
    u -= 1; v -= 1
    graph[u].append(v)
    graph[v].append(u)

for x in solve(N, A, graph):
    print x

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import copy
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

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

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

ans = [0] * n


def dfs(v, v_p, dp):
    # print(v, v_p, dp)
    ans[v] = len(dp)
    for v_next in graph[v]:
        if v_next == v_p:
            continue

        # print(dp)
        dp2 = copy(dp)
        if a[v_next] > dp2[-1]:
            dp2.append(a[v_next])
            dfs(v_next, v, dp2)
            dp2 = dp2[:len(dp2) - 1]
        else:
            idx = bisect_left(dp2, a[v_next])
            past = dp2[idx]
            dp2[idx] = a[v_next]
            dfs(v_next, v, dp2)
            dp2[idx] = past


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