Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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 = [0] * (N+1)
    seen[1] = 1
    ans = [0] * (N+1)
    ans[1] = 1
    LIS = []
    change = [[] for _ in range(N+1)]
    while que:
        v = que.pop()
        if v > 0:
            que.append(-v)
            a = A[v-1]
            if not LIS:
                LIS.append(a)
                change[v] = (0, -1)
            else:
                j = bisect_left(LIS, a)
                if j == len(LIS):
                    LIS.append(a)
                    ans[v] = len(LIS)
                    change[v] = (len(LIS) - 1, -1)
                else:
                    change[v] = (j, LIS[j])
                    LIS[j] = a
                    ans[v] = len(LIS)
            for u in adj[v]:
                if seen[u] == 0:
                    seen[u] = 1
                    que.append(u)
        else:
            v = -v
            i, x = change[v]
            if x == -1:
                LIS.pop()
            else:
                LIS[i] = x
    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):
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()


Fixed submission:
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 = [0] * (N+1)
    seen[1] = 1
    ans = [0] * (N+1)
    ans[1] = 1
    LIS = []
    change = [[] for _ in range(N+1)]
    while que:
        v = que.pop()
        if v > 0:
            que.append(-v)
            a = A[v-1]
            if not LIS:
                LIS.append(a)
                change[v] = (0, -1)
            else:
                j = bisect_left(LIS, a)
                if j == len(LIS):
                    LIS.append(a)
                    ans[v] = len(LIS)
                    change[v] = (len(LIS) - 1, -1)
                else:
                    change[v] = (j, LIS[j])
                    LIS[j] = a
                    ans[v] = len(LIS)
            for u in adj[v]:
                if seen[u] == 0:
                    seen[u] = 1
                    que.append(u)
        else:
            v = -v
            i, x = change[v]
            if x == -1:
                LIS.pop()
            else:
                LIS[i] = x
    for i in range(1, N+1):
        print(ans[i])


if __name__ == '__main__':
    main()