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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue_append = queue.append
    queue_append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            tmp_append = tmp.append
            A_now = A[i]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A_now > tmp[-1]:
                tmp_append(A_now)
            else:
                tmp[bisect.bisect_left(tmp, A_now)] = A_now
            queue_append((i,tmp))
            ans[i] = len(tmp)

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

    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    LIS = [A[0]]
    dist = [-1]*N
    dist[0] = 0
    ans = [0] * N
    ans[0] = 1
    queue = deque()
    queue.append((0,LIS))
    while queue:
        now, LIS_tmp = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            tmp = LIS_tmp[:]
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            if A[i] > tmp[-1]:
                tmp.append(A[i])
            else:
                tmp[bisect.bisect_left(tmp, A[i])] = A[i]
            queue.append((i,tmp))
            ans[i] = len(tmp)

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

    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

Buggy python submission (verdict: Runtime Error):
import sys
import bisect
input = sys.stdin.readline

N = int(input())
A = list(map(int, input().split()))
dp = [float('inf')] * (N + 1)
ans = [0] * N

def dfs(s,edge):
    global ans, dp
    index = bisect.bisect_left(dp[s], A[s])
    old = dp[index]
    length = bisect.bisect_left(dp[s], float('inf'))
    ans[index] = length
    for i in edge[s]:
        if i == s:
            continue
        dfs(i,edge)
    dp[index] = old

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for _ in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    dfs(0,edge)
    for i in range(N):
        print(ans[i])


if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    dp[0] = [A[0]]
    B[0] = [A[0]]
    queue = deque([0])
    while queue:
        now = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append(i)
            dp[i] += dp[now]
            if A[i] > dp[i][-1]:
                dp[i].append(A[i])
            else:
                dp[i][bisect.bisect_left(dp[i], A[i])] = A[i]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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



def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[] for _ in range(N)]
    B = [[] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    dp[0] = [A[0]]
    B[0] = [A[0]]
    queue = deque([0])
    while queue:
        now = queue.popleft()
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append(i)
            B[i] = B[now] + [A[i]]
            dp[i] += dp[now]
            if B[i][-1] > dp[i][-1]:
                dp[i].append(B[i][-1])
            else:
                dp[i][bisect.bisect_left(dp[i], B[i][-1])] = B[i][-1]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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



def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)
    dp = [[A[0]] for _ in range(N)]
    B = [[A[0]] for _ in range(N)]
    dist = [-1]*N
    dist[0] = 0
    queue = deque()
    queue.append([0,-1])
    while queue:
        Q = queue.popleft()
        now, pre = Q
        d = dist[now]
        for i in edge[now]:
            if dist[i] > -1:
                continue
            dist[i] = d + 1
            queue.append((i,now))
            B[i] = B[now] + [A[i]]
            dp[i] = dp[now].copy()
            if B[i][-1] > dp[i][-1]:
                dp[i].append(B[i][-1])
            else:
                dp[i][bisect.bisect_left(dp[i], B[i][-1])] = B[i][-1]

    for i in range(N):
        print(len(dp[i]))

    
if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()

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

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



def dijkstra_back(s,t,n,w,cost):
    #sからtへの最短経路の経路復元
    prev = [s] * n #最短経路の直前の頂点
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
        
        for i in range(n):
            if d[i] > d[v] + cost[v][i]: 
                d[i] = d[v] + cost[v][i]
                prev[i] = v
        
    path = [A[t]]
    while prev[t] != s:
        path.append(A[prev[t]])
        prev[t] = prev[prev[t]]
    path.append(A[s])
    path = path[::-1]
    return path

def main():
    cost = [[float("inf") for i in range(N)] for i in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        cost[u][v] = 1
        cost[v][u] = 1

    for i in range(N):
        seq = dijkstra_back(0,i,N,N-1,cost)
        LIS = [seq[0]]
        for i in range(len(seq)):
            if seq[i] > LIS[-1]:
                LIS.append(seq[i])
            else:
                LIS[bisect.bisect_left(LIS, seq[i])] = seq[i]
        
        print(len(LIS))

if __name__ == "__main__":
    main()

Fixed submission:
import sys
import bisect
from collections import deque
sys.setrecursionlimit(4100000)
input = sys.stdin.readline

def main():
    N = int(input())
    A = list(map(int, input().split()))
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        edge[u].append(v)
        edge[v].append(u)

    ans = [0] * (N + 1)
    LIS = [-1]
    
    def dfs(v, p = N):
        if A[v] > LIS[-1]:
            LIS.append(A[v])
            ans[v] = ans[p] + 1
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS.pop()
        else:
            ans[v] = ans[p]
            idx = bisect.bisect_left(LIS, A[v])
            old = LIS[idx]
            LIS[idx] = A[v]
            for u in edge[v]:
                if u == p:
                    continue
                dfs(u,v)
            LIS[idx] = old
    dfs(0)
    for i in range(N):
        print(ans[i])

if __name__ == "__main__":
    main()