Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

import bisect

n=int(input())
a= list(map(int, input().split()))
a1= [list(map(int, input().split())) for i in range(n-1)]

g=[[] for i in range(n)]

for x,y in a1:
    g[x-1].append(y-1)
    g[y-1].append(x-1)


vis = [0] * n
order = []
parent = [0] * n
s = [0]

while len(s):
    x = s.pop()
    vis[x] = 1
    order.append(x)
    for y in g[x]:
        if vis[y]: continue
        s.append(y)
        parent[y] = x


ans=[0]*n
LIS = [[0] for i in range(n)]

for x in order:
    LIS[x]=LIS[parent[x]][:]
    if a[x] > LIS[x][-1]:
        LIS[x].append(a[x])
    else:
        LIS[x][bisect.bisect_left(LIS[x], a[x])] = a[x]
    ans[x]=len(LIS[x])-1

for i in ans:
    print(i)

Fixed submission:
from bisect import bisect_left
from collections import deque

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

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
INF=float('inf')
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i,ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import collections
from collections import deque

n=int(input())
a= list(map(int, input().split()))
a1= [list(map(int, input().split())) for i in range(n-1)]

g=[[] for i in range(n)]

for x,y in a1:
    g[x-1].append(y-1)
    g[y-1].append(x-1)


vis = [0] * n
order = []
parent = [0] * (n + 1)
s = [0]

while len(s):
    x = s.pop()
    vis[x] = 1
    order.append(x)
    for y in g[x]:
        if vis[y]: continue
        s.append(y)
        parent[y] = x


ans=[0]*n
LIS = [[0] for i in range(n)]

for x in order:
    LIS[x]=LIS[parent[x]][:]
    if a[x] > LIS[x][-1]:
        LIS[x].append(a[x])
    else:
        LIS[x][bisect.bisect_left(LIS[x], a[x])] = a[x]
    ans[x]=len(LIS[x])-1

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

Fixed submission:
from bisect import bisect_left
from collections import deque

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

graph = [[] for _ in range(N)]
for u, v in X:
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
INF=float('inf')
dp = [INF] * (N + 1)
dp[0] = -INF
rb = [[] for _ in range(N)]
ans = [0] * N

# DFS
q = deque([(0, 0)])  # (current, parent)
while q:
    u, p = q.pop()

    # Roll back
    if p is None:
        i, x = rb[u].pop()
        dp[i] = x
        continue

    # Update dp
    i = bisect_left(dp, A[u])
    rb[u].append((i, dp[i]))
    dp[i] = A[u]

    # Calc ans
    ans[u] = max(i,ans[p])

    # Go to next
    q.append((u, None))
    for v in graph[u]:
        if v == p:
            continue
        q.append((v, u))

print(*ans)