Problem p02698 (python)

Fixed submission:
from collections import deque
from bisect import bisect_left
import sys
sys.setrecursionlimit(10**7)
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)
stack=deque([])
inf=10**18
lis=[inf]*(n+1)
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    idx=bisect_left(lis,a[s])
    stack.append((idx,lis[idx]))
    lis[idx]=a[s]
    ans[s]=bisect_left(lis,inf)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    lis[idx]=val
dfs(0)
#print(lis)
for i in range(n):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right
import sys
sys.setrecursionlimit(10**7)
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)
stack=deque([])
lis=[]
ans=[0 for _ in range(n)]
visited=[True]*n
#print(edge)
def dfs(s):
    visited[s]=False
    if len(lis)==0 or lis[-1]<a[s]:
        lis.append(a[s])
        stack.append((len(lis)-1,-1))
    else:
        #print(lis)
        idx=bisect_right(lis,a[s])
        #print(idx)
        stack.append((idx,lis[idx]))
        lis[idx]=a[s]
    ans[s]=len(lis)
    for x in edge[s]:
        if visited[x]:
            dfs(x)
    idx,val=stack.pop()
    if val==-1:
        del lis[-1]
    else:
        lis[idx]=val
dfs(0)
for i in range(n):
    print(ans[i])

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right
from copy import deepcopy
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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            if visited[nx]:
                if a[nx]>lis[x][-1]:
                    lis[nx]=lis[x]+[a[nx]]
                else:
                    idx=bisect_right(lis[x],a[nx])
                    cur=deepcopy(lis[x])
                    cur[idx]=a[nx]
                    lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right
from copy import deepcopy
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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            if visited[nx]:
                if a[nx]>lis[x][-1]:
                    lis[nx]=lis[x]+[a[nx]]
                else:
                    idx=bisect_right(cur,a[nx])
                    cur=deepcopy(lis[x])
                    cur[idx]=a[nx]
                    lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right
from copy import deepcopy
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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            cur=deepcopy(lis[x])
            if visited[nx]:
                if a[nx]>cur[-1]:
                    cur.append(a[nx])
                else:
                    idx=bisect_right(cur,a[nx])
                    cur[idx]=a[nx]
                lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
    return
dfs()
for i in range(n):
    print(len(lis[i]))

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right
from copy import deepcopy
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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            cur=deepcopy(lis[x])
            if visited[nx]:
                if a[nx]>cur[-1]:
                    cur.append(a[nx])
                else:
                    idx=bisect_right(cur,a[nx])
                    cur[idx]=a[nx]
                lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
dfs()
for i in range(n):
    print(len(lis[i]))

Buggy submission (verdict: Runtime Error):
from collections import deque
from bisect import bisect_right
from copy import deepcopy
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)
visited=[True]*n
lis=[[] for _ in range(n)]
def dfs():
    stack=deque([0])
    visited[0]=False
    lis[0]=[a[0]]
    while stack:
        x=stack.pop()
        for nx in edge[x]:
            cur=deepcopy(lis[x])
            if visited[nx]:
                if a[nx]>cur[-1]:
                    cur.append(a[nx])
                else:
                    idx=bisect_right(cur,a[nx])
                    cur[idx]=a[nx]
                lis[nx]=cur
                visited[nx]=False
                stack.append(nx)
dfs()
for i in range(n):
    print(len(lis[i]))