Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]
 
    A = [0]+list(map(int, input().split()))
 
    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)
 
    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1
 
    d = deque()
    d.append((1, [0, A[1]]))
 
    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            if dp[-1] < A[i]:
                dp.append(A[i])
                d.append((i, dp.copy()))
                dist[i] = len(dp)-1
                dp.pop()
            else:
                bis = bisect.bisect_left(dp, A[i])
                updatetask=dp[bis]
                dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp.copy()))
                dp[bis]=updatetask
 
    print(*dist[1:], sep="\n")
 
if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        graph2=[]
        for i in graph[v]:
            if dist[i] == -1:
                graph2.append(i)
        for index, i in enumerate(graph2,1):
            if index==len(graph2):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                ndp=dp.copy()
                if dp[-1] < A[i]:
                    ndp.append(A[i])
                else:
                    bis = bisect.bisect_left(ndp, A[i])
                    ndp[bis] = A[i]
                dist[i] = len(ndp)-1
                d.append((i, ndp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        for index, i in enumerate(graph[v],1):
            if dist[i] != -1:
                continue
            if index==len(graph[v]):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                ndp=dp.copy()
                if dp[-1] < A[i]:
                    ndp.append(A[i])
                else:
                    bis = bisect.bisect_left(ndp, A[i])
                    ndp[bis] = A[i]
                dist[i] = len(ndp)-1
                d.append((i, ndp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        for index, i in enumerate(graph[v],1):
            if dist[i] != -1:
                continue
            if index==len(graph[v]):
                if dp[-1] < A[i]:
                    dp.append(A[i])
                else:
                    bis = bisect.bisect_left(dp, A[i])
                    dp[bis] = A[i]
                dist[i] = len(dp)-1
                d.append((i, dp))
            else:
                newdp = update(dp, A[i])
                dist[i] = len(newdp)-1
                d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()

Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            newdp = update(dp, A[i])
            dist[i] = len(newdp)-1
            d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp

def main():
    n = int(input())
    graph = [[] for _ in range(n+1)]

    A = [0]+list(map(int, input().split()))

    for i in range(n-1):
        a, b = map(int, input().split())
        graph[a].append(b)
        graph[b].append(a)

    dist = [-1] * (n+1)
    dist[0] = 0
    dist[1] = 1

    d = deque()
    d.append((1, [0, A[1]]))

    while d:
        v, dp = d.popleft()
        for i in graph[v]:
            if dist[i] != -1:
                continue
            newdp = update(dp, A[i])
            dist[i] = len(newdp)-1
            d.append((i, newdp))

    print(*dist[1:], sep="\n")

if __name__ == '__main__':
    main()


Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()


n = int(input())

graph = [[] for _ in range(n+1)]

A = [0]+list(map(int, input().split()))

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 1

d = deque()
d.append((1, [0, A[1]]))


def update(dp, AA):
    ndp = dp.copy()
    if ndp[-1] < AA:
        ndp.append(AA)
    else:
        bis = bisect.bisect_left(ndp, AA)
        ndp[bis] = AA
    return ndp


while d:
    v, dp = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        newdp = update(dp, A[i])
        dist[i] = len(newdp)-1
        d.append((i, newdp))

ans = dist[1:]
print(*ans, sep="\n")

Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")

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

n=int(input())

graph = [[] for _ in range(n+1)]

A=[0]+list(map(int, input().split()))

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 1

d = deque()
d.append((1,[0,A[1]]))

def update(dp,AA):
    ndp=dp.copy()
    if ndp[-1]<AA:
        ndp.append(AA)
    else:
        bis=bisect.bisect_left(ndp, AA)
        ndp[bis]=AA
    return ndp

while d:
    v,dp = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        newdp=update(dp,A[i])
        dist[i] = len(newdp)-1
        d.append((i,newdp))

ans = dist[1:]
print(*ans, sep="\n")

Fixed submission:
from collections import deque
import sys
import bisect
def input(): return sys.stdin.readline().rstrip()

n=int(input())
A=[0]+list(map(int, input().split()))

graph = [[] for _ in range(n+1)]

for i in range(n-1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)

visited = [-1] * (n+1)
visited[0] = 0
visited[1] = 1

d = deque()
d.append(1)
dp=[10**10]*(n+1)
dp[0]=0
dp[1]=A[1]
update_task=[() for _ in range(n+1)]
update_task[1]=(1,0)
while d:
    v = d[-1]
    if graph[v] == []:
        d.pop()
        index,atai=update_task[v]
        dp[index]=atai
    else:
        i = graph[v].pop()
        if visited[i] != -1:
            continue
        bis = bisect.bisect_left(dp, A[i])
        update_task[i]=(bis,dp[bis])
        dp[bis] = A[i]
        visited[i] = bisect.bisect_left(dp, 10**10-100)-1
        d.append(i)

print(*visited[1:], sep="\n")