Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res


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

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

res = eular_tour(tree, 0)

array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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

Fixed submission:
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    par = {root: -1}
    stack = [root]
 
    while stack:
        v = stack.pop()
        if v >= 0:  # 行きがけ順の処理
            trail.append(v)
            stack.append(~v)
            for nxt_v in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append(nxt_v)
 
        else:  # 帰りがけ順の処理
            if ~v == root:
                continue
            trail.append(-par[~v])
 
    return trail


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

tree = [[] for i in range(n)]
for u, v in info:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

res = euler_tour(tree, 0)
array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if ind > 0:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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

Buggy python submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res


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

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

res = eular_tour(tree, 0)

array_ind = [0]
array_val = [a[0]]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        array_val.append(val)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        del array_val[-1]
        pos = stack1.pop()
        val = stack2.pop
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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

Fixed submission:
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    par = {root: -1}
    stack = [root]
 
    while stack:
        v = stack.pop()
        if v >= 0:  # 行きがけ順の処理
            trail.append(v)
            stack.append(~v)
            for nxt_v in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append(nxt_v)
 
        else:  # 帰りがけ順の処理
            if ~v == root:
                continue
            trail.append(-par[~v])
 
    return trail


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

tree = [[] for i in range(n)]
for u, v in info:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

res = euler_tour(tree, 0)
array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if ind > 0:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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

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


def eular_tour(tree: list, root: int):
    """根をrootとしたときの頂点に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    res = []
    begin = [-1] * n
    end = [-1] * n
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        pos = q.pop()
        res.append(pos)
        end[pos] = len(res)
        if begin[pos] == -1:
            begin[pos] = len(res) - 1
        for next_pos in tree[pos]:
            if visited[next_pos]:
                continue
            else:
                visited[next_pos] = True
                q.append(pos)
                q.append(next_pos)
    return res, begin, end


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

tree = [[] for i in range(n)]
for aa, b in info:
    aa -= 1
    b -= 1
    tree[aa].append(b)
    tree[b].append(aa)

res, _, _ = eular_tour(tree, 0)

array_ind = [0]
array_val = [a[0]]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack = []
for ind in res[1:]:
    if len(array_ind) <= 1 or array_ind[-2] != ind:
        val = a[ind]
        array_ind.append(ind)
        array_val.append(val)
        if val > lis_array[-1]:
             lis_array.append(val)
             stack.append((-1, -1))
        else:
            pos = bisect_left(lis_array, val)
            stack.append((pos, lis_array[pos]))
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        del array_val[-1]
        pos, val = stack.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val
for i in range(n):
    print(ans[i])

Fixed submission:
from collections import deque
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline


def euler_tour(tree: list, root: int):
    """根をrootとしたときの辺に対するオイラーツアーを行う
    posの部分木が区間[begin[pos], end[pos])に対応する
    """
    n = len(tree)
    trail = []
    par = {root: -1}
    stack = [root]
 
    while stack:
        v = stack.pop()
        if v >= 0:  # 行きがけ順の処理
            trail.append(v)
            stack.append(~v)
            for nxt_v in tree[v]:
                if nxt_v not in par:
                    par[nxt_v] = v
                    stack.append(nxt_v)
 
        else:  # 帰りがけ順の処理
            if ~v == root:
                continue
            trail.append(-par[~v])
 
    return trail


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

tree = [[] for i in range(n)]
for u, v in info:
    u -= 1
    v -= 1
    tree[u].append(v)
    tree[v].append(u)

res = euler_tour(tree, 0)
array_ind = [0]
lis_array = [a[0]]
ans = [0] * n
ans[0] = 1

# (-1, -1): remove array
# (pos, val): change array
stack1 = []
stack2 = []
for ind in res[1:]:
    if ind > 0:
        val = a[ind]
        array_ind.append(ind)
        if val > lis_array[-1]:
            lis_array.append(val)
            stack1.append(-1)
            stack2.append(-1)
        else:
            pos = bisect_left(lis_array, val)
            stack1.append(pos)
            stack2.append(lis_array[pos])
            lis_array[pos] = val
        ans[ind] = len(lis_array)
    else:
        del array_ind[-1]
        pos = stack1.pop()
        val = stack2.pop()
        if pos == -1:
            del lis_array[-1]
        else:
            lis_array[pos] = val

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