Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0:
        old = inf
        i = len(LIS)
        LIS.append(x)
    elif x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x
    if inf in LIS:
        a = LIS.index(inf)
    else:
        a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])


Fixed submission:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0:
        old = inf
        i = len(LIS)
        LIS.append(x)
    elif x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x
    if inf in LIS:
        a = LIS.index(inf)
    else:
        a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])


Fixed submission:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    x = As[v]
    if prev != -1 and x > LIS[prev][-1]:
        l = copy.copy(LIS[prev])
        l.append(x)
        LIS[v] = l
    elif prev != -1:
        l = copy.copy(LIS[prev])
        l[bisect.bisect_left(l, x)] = x
        LIS[v] = l
    else:
        LIS[v] = [x]
    ans_array[v] = len(LIS[v])
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = [[] for i in range(N)]
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])


Fixed submission:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        x = As[u]
        if x > LIS[v][-1]:
            LIS[u] = LIS[v] + [x]
        else:
            l = copy.copy(LIS[v])
            l[bisect.bisect_left(l, x)] = x
            LIS[u] = l
        ans_array[u] = len(LIS[u])
        dfs(u,v)

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = [[] for i in range(N)]
LIS[0].append(As[0])
ans_array = [0] * N
ans_array[0] = 1
dfs(0)
for i in range(N):
    print(ans_array[i])


Fixed submission:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

def dfs(v,prev = -1):
    for u in graph[v]:
        if u == prev:
            continue
        x = As[u]
        if x > LIS[v][-1]:
            LIS[u] = LIS[v] + [x]
        else:
            l = copy.copy(LIS[v])
            l[bisect.bisect_left(l, x)] = x
            LIS[u] = l
        ans_array[u] = len(LIS[u])
        dfs(u,v)

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = [[] for i in range(N)]
LIS[0].append(As[0])
ans_array = [0] * N
ans_array[0] = 1
dfs(0)
for i in range(N):
    print(ans_array[i])


Fixed submission:
import sys
import bisect
import copy
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]
inf = 10**9+1

def dfs(v,prev = -1):
    x = As[v]
    if len(LIS) == 0 or x > LIS[-1]:
        old = inf
        i = len(LIS)
        LIS.append(x)
    else:
        i = bisect.bisect_left(LIS, x)
        old = LIS[i]
        LIS[i] = x

    a = len(LIS)
    ans_array[v] = a
    for u in graph[v]:
        if u == prev:
            continue
        dfs(u,v)
    if old == inf:
        LIS.pop(-1)
    else:
        LIS[i] = old

N = int(input())
As = list(map(int,input().split()))
graph = [[] for _ in range(N)]

for i in range(N-1):
    a,b = list(map(int,input().split()))
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
LIS = []
ans_array = [0] * N
dfs(0)
for i in range(N):
    print(ans_array[i])