Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        l[i] = A
        ans[v] = l.index(inf)
        visited[v] = True

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







Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect

input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

lis = [0] * (N+1)
lis[1] = 1

def f(v,l,k):
    if visited[v]:
        return
    visited[v] = True
    A = a[v-1]
    i = bisect.bisect_left(l,A)
    if k < i:
        l.append(inf)
        k += 1
    l[i] = A 
    lis[v] = k
    #lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:],k)

l = [inf] * 1
f(1,l,0)

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







Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
import numpy as np

input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = np.array([inf] * (N+1))

lis = [0] * (N+1)
lis[1] = 1

def f(v,l,k):
    if visited[v]:
        return
    visited[v] = True
    A = a[v-1]
    #i = bisect.bisect_left(l,A)
    i = np.searchsorted(l,A)
    l[i] = A 
    if k < i:
        k += 1
    lis[v] = k
    #lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,np.copy(l),k)

l = [inf] * (N+1)
f(1,l,0)

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







Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect

input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

lis = [0] * (N+1)
lis[1] = 1

def f(v,l,k):
    if visited[v]:
        return
    visited[v] = True
    A = a[v-1]
    i = bisect.bisect_left(l,A)
    l[i] = A 
    if k < i:
        k += 1
    lis[v] = k
    #lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:],k)

l = [inf] * (N+1)
f(1,l,0)

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







Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
euler = [1]
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)


lis = [0] * (N+1)
lis[1] = 1

def f(v,l):
    if visited[v]:
        return
    visited[v] = True
    i = bisect.bisect_right(l,a[v-1])
    l[i] = a[v-1]
    lis[v] = l.index(inf) - 1
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:])

l = [inf] * (N+1)
l[0] = a[0]
f(1,l)

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







Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

dq = deque([1])
euler = [1]
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)


lis = [0] * (N+1)
lis[1] = 1

def f(v,l):
    if visited[v]:
        return
    visited[v] = True
    i = bisect.bisect(l,a[v-1])
    l[i] = a[v-1]
    lis[v] = l.index(inf)
    for nv in g[v]:
        if not visited[nv]:
            f(nv,l[:])

l = [inf] * (N+1)
l[0] = a[0]
f(1,l)

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







Fixed submission:
import sys
sys.setrecursionlimit(10**9)
from collections import defaultdict,deque
import bisect
input = sys.stdin.readline

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

g = defaultdict(list)
for i in range(N-1):
    u, v = map(int,input().split())
    g[u].append(v)
    g[v].append(u)

def eulerTour(g,s):
    n = len(g)
    dq = [s]
    ls = [-1]*(n+1)
    rs = [-1]*(n+1)
    index = []
    visited = [False]*(n+1)
    def dfs(v):
        visited[v] = True
        ls[v] = len(index)
        index.append(v)
        for nv in g[v]:
            if not visited[nv]:
                dfs(nv)
        rs[v] = len(index)
        index.append(v)
    dfs(s)
    return ls,rs,index

ls,rs,index = eulerTour(g,1)
dq = deque([1])
visited = [False]*(N+1)

inf = 10**10
l = [inf] * (N+1)

ans = [0] * (N+1)
ans[1] = 1

visited = [False]*(N+1)
rollback = []

k = 1
for v in index:
    if visited[v]:
        i, pa = rollback.pop()
        l[i] = pa
        if pa == inf:
            k -= 1
    else:
        A = a[v-1]
        i = bisect.bisect_left(l,A)
        rollback.append((i,l[i]))
        if k <= i:
            k += 1
        l[i] = A
        #ans[v] = l.index(inf)
        ans[v] = k
        visited[v] = True


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