Buggy python submission (verdict: Time Limit Exceeded):
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:
            nxt_lis = lis
        else:
            nxt_lis = list(lis)
        if idx == len(nxt_lis):
            nxt_lis.append(A[cur])
        else:
            nxt_lis[idx] = A[cur]
        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()


Fixed submission:
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, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

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


Fixed submission:
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, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

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


Fixed submission:
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, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

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


Fixed submission:
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, [], 0)]
    history = []
    while len(q):
        cur, prev, lis, depth = q.pop()
        while depth < len(history):
            pos, val = history.pop()
            if val is None:
                lis.pop()
            else:
                lis[pos] = val
        idx = bisect_left(lis, A[cur])
        if idx == len(lis):
            history.append((idx, None))
            lis.append(A[cur])
        else:
            history.append((idx, lis[idx]))
            lis[idx] = A[cur]
        ans[cur] = len(lis)
        for nxt in adj[cur]:
            if nxt == prev:
                continue
            q.append((nxt, cur, lis, depth+1))
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()