Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03164 (python)

Fixed submission:
INF = 10**10 - 1

#指定数分の複数の整数を順番に受けてリストに入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
Vsum = 0
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())
    Vsum += v[i]

#dpの初期化
dp = [[INF] * (Vsum+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for vv in range(1,Vsum+1):
        if v[i] > vv:
            dp[i][vv] = dp[i-1][vv]
        else:
            dp[i][vv] = min(dp[i-1][vv],dp[i-1][vv-v[i]]+w[i])
    #print(dp[i])

Vmax = 0
for vv in range(1,Vsum+1):
    if dp[N][vv] <= Wmax:
        Vmax = vv
print(Vmax)

Buggy submission (verdict: Runtime Error):
INF = 10**10 - 1


#指定数分の３つの整数を順番に受けてリストに入力
# スペース区切りの整数入力
N,Wmax = map(int, input().split())
w = [0]*(N+1)
v = [0]*(N+1)
for i in range(1,N+1):
    w[i],v[i] = map(int, input().split())

#dpの初期化
dp = [[-INF] * (Wmax+1) for i in range(N+1)]
for i in range(0,N+1):
    dp[i][0] = 0
#print(dp[0])

for i in range(1,N+1):
    for ww in range(1,Wmax+1):
        if w[i] > ww:
            dp[i][ww] = dp[i-1][ww]        
        else:
            dp[i][ww] = max(dp[i-1][ww],dp[i-1][ww-w[i]]+v[i])
    #print(dp[i])

Vmax = 0
for ww in range(1,Wmax+1):
    Vmax = max(Vmax,dp[N][ww])
print(Vmax)
Problem p03165 (python)

Fixed submission:
INF = 10**10 - 1 #無限大
SMAX = 3000 + 10

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (SMAX) for i in range(SMAX)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)

Buggy submission (verdict: Runtime Error):
INF = 10**10 - 1 #無限大
SMAX = 3000 + 1

# 文字列入力
s1 = input()
s2 = input()

'''
dpの初期化
s1の文字列位置を一次軸、s2の文字列位置を二次軸に取り
その値として：LCSの最長値として更新していく
　　　　　　　初期値はすべて０
'''
dp = [ [0] * (len(s2)+1) for i in range(len(s2)+1)]

for s1pos in range(1,len(s1)+1):
    s1s = s1[s1pos-1:s1pos]
    for s2pos in range(1,len(s2)+1):
        s2s = s2[s2pos-1:s2pos]
        if s1s == s2s:
            dp[s1pos][s2pos] = dp[s1pos-1][s2pos-1] + 1
        dp[s1pos][s2pos] = max(dp[s1pos][s2pos],dp[s1pos][s2pos-1],dp[s1pos-1][s2pos])
    #print("s1pos=",s1pos,"dp=",dp[s1pos])

#print("LCS_len",dp[len(s1)][len(s2)])

res = ""
s1pos = len(s1)
s2pos = len(s2)
while (s1pos > 0 and s2pos > 0):
    # (s1pos-1, s2pos) -> (s1pos, s2pos) と更新されていた場合
    if (dp[s1pos][s2pos] == dp[s1pos-1][s2pos]):
        s1pos -= 1 # DP の遷移を遡る
    # (s1pos, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    elif (dp[s1pos][s2pos] == dp[s1pos][s2pos-1]):
        s2pos -= 1 # DP の遷移を遡る
    # (s1pos-1, s2pos-1) -> (s1pos, s2pos) と更新されていた場合
    else:
        res = s1[s1pos-1:s1pos] + res # 該当文字を取得
        s1pos -= 1 # DP の遷移を遡る
        s2pos -= 1 # DP の遷移を遡る

print(res)
Problem p03166 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**5)

# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+10)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Buggy submission (verdict: Runtime Error):
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+10)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Buggy submission (verdict: Runtime Error):
from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+1)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)

Buggy submission (verdict: Runtime Error):
from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+1)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)
Problem p03168 (python)

Fixed submission:
N = int(input())
p_f = [0.0]
p_b = [0.0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

#一次軸：コイントスの回数、二次軸：勝ち数、値：発生確率
dp = [[0.0] * (N+1) for i in range(N+1)]
dp[0][0] = 1.0

def cointoss(n_toss):
    global p_majority
    for i in range(n_toss):
        dp[n_toss][i+1] += dp[n_toss-1][i] * p_f[n_toss]
        dp[n_toss][i  ] += dp[n_toss-1][i] * p_b[n_toss]

for i in range(1,N+1):
    cointoss(i)

p_majority = 0.0
n_majority = N // 2 + 1

for i in range(n_majority,N+1):
    p_majority += dp[N][i]

print(p_majority)

Buggy submission (verdict: Runtime Error):
N = int(input())
p_f = [0]
p_b = [0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

p_majority = 0.0
n_majority = N // 2 + 1

def cointoss(n_toss,n_front,n_back,p):
    global p_majority
    n_toss += 1
    #print(n_toss,n_front,n_back,p,p_majority,n_majority)
    if n_front+1 == n_majority:
        p_majority = p_majority + p * p_f[n_toss]
    else:
        cointoss(n_toss, n_front+1, n_back, p*p_f[n_toss])
    if n_back+1 == n_majority:
        return
    cointoss(n_toss, n_front, n_back+1, p*p_b[n_toss])

cointoss(0,0,0,1.0)
print(p_majority)
Problem p03296 (python)

Fixed submission:
n = int(input())
x = input().split(' ')
l = [int(i) for i in x]

c = 0

i = 0
while i+1 < n:
    if l[i] == l[i+1]:
        c += 1
        i += 2
    else:
        i += 1
print(c)

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input().split(' ')
l = [int(i) for i in x]

c = 0


for i in range(1,n):
    if not boon and l[i] == l[i-1]:
        c += 1
        boon = True
    else:
        boon = False

print(c)

Buggy submission (verdict: Runtime Error):
n = int(input())
x = input().split(' ')
l = [int(i) for i in x]

c = 0
i = 0
def s():
    while i+2 < len(l):
        if l[i] == l[i+1]:
            if l[i+1] == l[i+2]:
                c += 1
                i += 2
            else:
                c += 1
                i += 2
        else:
            i += 1
    
    print(c)
    return 0

s()
Problem p02687 (python)

Fixed submission:
a = input()

if a == "ABC":
    print("ARC")
elif a == "ARC":
    print("ABC")

Buggy submission (verdict: Runtime Error):
a = input()

if a == "ABC":
    print("ARC")
else a == "ARC":
    print("ABC")
Problem p02999 (python)

Fixed submission:

X, A = map(int,input().split())


if X < A:
    print("0")
else:
    print("10")

Buggy submission (verdict: Runtime Error):
X, A = map(int,input.sprit())


if X > A:
  print("10")
  else:
    print("0")
Problem p02922 (python)

Fixed submission:
A, B = map(int, input().split())

S = 1
ans = 0
while S < B:
	S += A - 1
	ans += 1
print (ans)

Buggy submission (verdict: Runtime Error):
A, B = map(int, input().split()):

S = 1
ans = 0
while S < B:
	S += A - 1
	ans += 1
print (ans)
Problem p03238 (python)

Fixed submission:
n = int(raw_input())
if n == 1:
    print "Hello World"
else:
    print int(raw_input()) + int(raw_input())

Buggy submission (verdict: Runtime Error):
n = int(raw_input())
pts = [map(int, raw_input().split()) for i in xrange(n)]

for i in xrange(105):
    for j in xrange(105):
        H = -7
        ok = True
        for k in pts:
            if max(H - abs(k[0] - i) - abs(k[1] - j), 0) == k[2]:
                continue
            elif H < 1:
                H = k[2] + abs(k[0] - i) + abs(k[1] - j)
            else:
                ok = False
        if ok:
            print i, j, max(H, 1)
            exit(0)

Buggy submission (verdict: Runtime Error):
n, m = map(int, raw_input().split())

target = m / n

while True:
    if (m - target * n) % target == 0:
        print target
        exit(0)
    target -= 1
Problem p04043 (python)

Fixed submission:
A= list(map(int, input().split()))
if A.count(5) == 2 and A.count(7) == 1:
    print('YES')
else:
    print('NO')

Buggy submission (verdict: Runtime Error):
A= list(int(input().split(' ')))
if A.count(5) == 2 and A.coutn(7) == 1:
  print('YES')
else:
  print('NO')
Problem p02700 (python)

Fixed submission:
#ABC164 B
p = [int(x) for x in input().split()]

takahashi_turn = True
while (p[0]>0) and (p[2]>0):
    if takahashi_turn:
        p[2] = p[2] - p[1]
    else:
        p[0] = p[0] - p[3]
    takahashi_turn = not takahashi_turn

if p[0] > 0:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
#ABC164 B
p = [int(x) for x in input().split()]

takahashi_turn = True
while (p[0]<=0) or (p[2]<=0):
    if takahashi_turn:
        p[2] = p[2] - p[1]
    else:
        p[0] = p[0] - p[3]
    takahashi_turn = ! takahashi_turn

if p[0] > 0:
    print("Yes")
else:
    print("No")

Buggy submission (verdict: Runtime Error):
#ABC164 B
p = [int(x) for x in input().split()]

takahashi_turn = True
while (p[0]<=0) or (p[2]<=0):
    if takahashi_turn:
        p[2] = p[2] - p[1]
    else:
        p[0] = p[0] - p[3]
    takahashi_turn = ! takahashi_turn

if p[0] > 0:
    print("Yes")
else:
    print("No")
Problem p02767 (python)

Fixed submission:
P=int(input())
X=list(map(int,input().split()))
l=[]
for j in range(min(X),max(X)+1):
    ans = [(i-j)**2 for i in X ]
    l.append(sum(ans))
print(min(l))

Buggy submission (verdict: Runtime Error):
P=int(input())
X=list(map(int,input().split()))
l=[]
for j in range(min(X),max(X)):
    ans = [(i-j)**2 for i in X ]
    l.append(sum(ans))
print(min(l))
Problem p02957 (python)

Fixed submission:
a,b=map(int,input().split())
print((a+b)//2 if (a+b)%2==0 else "IMPOSSIBLE")

Buggy submission (verdict: Runtime Error):
n=int(input())
l=list(map(int,input().split()))
count=0
for i in range(1,n+1)
    if l[i-1]!=i:
        count+=1
print("YES" if count==0 or count==2 else "NO")
Problem p02958 (python)

Fixed submission:
n=int(input())
l=list(map(int,input().split()))
count=0
for i in range(1,n+1):
    if l[i-1]!=i:
        count+=1
print("YES" if count==0 or count==2 else "NO")

Buggy submission (verdict: Runtime Error):
n=int(input())
l=list(map(int,input().split()))
count=0
for i in range(1,6):
    if l[i-1]!=i:
        count+=1
print("YES" if count==0 or count==2 else "NO")
Problem p03085 (python)

Fixed submission:
b = input()

if b == "A":
    result = "T"
elif b == "C":
    result = "G"
elif b == "G":
    result = "C"
elif b == "T":
    result = "A"

print(result)

Buggy submission (verdict: Runtime Error):
# AGCT -> 0123
# 条件
# # 文字 0-3のみ
# # 文字 0-2を含まない
# # 隣同士swapしても0-2を含まない
# 012, 102, 021, 0?12, 01?2が含まずに条件を満たす文字列 Sの数を求める

# S + 0
# S + 1 -> 021の可能性
# S + 2 -> 0?12, 01?2の可能性
# S + 3
# Sの手前3文字を見れば良い -> DP
# # DP: 動的計画法, 計算をまとめるだけのテクニック
# # 文字数, 最後から3文字目, 2文字目, 1文字目の情報をもつDP

# ACが来たらカウントする

import numpy as np

N = int(input())

mod = 10 ** 9 + 7
# メモ化: [{}, {}, {}, {}]
memo = np.zeros((N + 1, 4, 4, 4))
memo[0][3][3][3] = 1

# 文字列の文字数
for c in range(N):
    # 最後から1文字目の文字
    for i in range(4):
        # 最後から2文字目の文字
        for j in range(4):
            # 最後から3文字目の文字
            for k in range(4):
                # 新しく追加する文字
                for a in range(4):
                    # ダメな5つの条件をカットする
                    # 012, 102, 021, 0?12, 01?2
                    if a == 1 and i == 2 and j == 0:
                        continue
                    if a == 2 and i == 1 and j == 0:
                        continue
                    if a == 2 and i == 0 and j == 1:
                        continue
                    if a == 2 and j == 1 and k == 0:
                        continue
                    if a == 2 and i == 1 and k == 0:
                        continue
                    # ダメな条件を抜けたら，aを足した文字列を作れる
                    memo[c + 1][a][i][j] += memo[c][i][j][k]
                    memo[c + 1][a][i][j] %= mod

# 長さNの全部の答えをまとめる処理
ans = 0
# 最後から1文字目の文字
for i in range(4):
    # 最後から2文字目の文字
    for j in range(4):
        # 最後から3文字目の文字
        for k in range(4):
            ans += memo[N][i][j][k]
            ans %= mod
print(int(ans))
Problem p03636 (python)

Fixed submission:
s = str(input())

print("{}{}{}".format(s[0], len(s) - 2, s[-1]))

Buggy submission (verdict: Runtime Error):
s = str(input())

print("{}{}{}".format(s[0], len(s) - 2), s[-1])
Problem p03644 (python)

Fixed submission:
m = int(input())
a = 1
for c in range(7):
  if (2 ** c) > m:
    break
  a = (2 ** c)
 
print(a)

Buggy submission (verdict: Runtime Error):
import sys

N = int(sys.stdin.readline())

sorted_list = [1, 2, 4, 8, 16, 32, 64, N][::1]
min_index = sorted_list[sorted_list.index(N) + 1]
print(min_index)

Buggy submission (verdict: Runtime Error):
import sys

N = int(sys.stdin.readline())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


sorted_list = [2, 4, 8, 16, 32, 64, N][::1]
min_index = sorted_list[sorted_list.index(N) + 1]

cnt = 0
min_cnt = dev(min_index)
for i in reversed(range(min_index, N + 1, 2)):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        print(i)
        exit()
print(min_index)

Buggy submission (verdict: Runtime Error):
import sys

N = int(sys.stdin.readline())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


sorted_list = sorted([2, 4, 8, 16, 32, 64, N], reverse=True)
min_index = sorted_list[sorted([2, 4, 8, 16, 32, 64, N], reverse=True).index(N) + 1]

cnt = 0
min_cnt = dev(min_index)
for i in range(min_index, N + 1, 2):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        print(i)
        exit()
print(min_index)

Buggy submission (verdict: Runtime Error):
import sys

N = int(sys.stdin.readline())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


min_cnt = 0
sorted_list = sorted([2, 4, 8, 16, 32, 64, N], reverse=True)
min_index = sorted_list[sorted([2, 4, 8, 16, 32, 64, N], reverse=True).index(N) + 1]

for i in range(min_index, N + 1, 2):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        min_i = i
        min_cnt = result
print(min_i)

Buggy submission (verdict: Runtime Error):
import sys
N = int(sys.stdin.readline())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


min_cnt = 0
for i in reversed(range((N + 1)//2, N + 1, 2)):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        min_i = i
        min_cnt = result
print(min_i)

Buggy submission (verdict: Runtime Error):
import sys
N = int(sys.stdin.readline())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


min_cnt = 0
for i in range(2, N + 1, 2):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        min_i = i
        min_cnt = result
print(min_i)

Buggy submission (verdict: Runtime Error):
N = int(input())


def dev(x):
    global cnt
    if x % 2 == 0:
        cnt += 1
        dev(x / 2)
    return cnt


min_cnt = 0
for i in range(2, N + 1, 2):
    cnt = 0
    result = dev(i)
    if min_cnt < result:
        min_i = i
        min_cnt = result
print(min_i)
Problem p03796 (python)

Fixed submission:
N = int(input())

power = 1
mod = 10 ** 9 + 7

for i in range(1, N + 1):
    power *= i
    power %= mod
print(power)

Buggy submission (verdict: Runtime Error):
N = int(input())

power = 1
mod = 10 ** 9 + 7

for i in range(1, N + 1):
    power *= i
	power %= mod
print(power)
Problem p02690 (python)

Fixed submission:
x = int(input())
a=0
b=0
for i in range(-400,400):
    for j in range(-400,400):
        if i**5 - j**5 == x:
            a = i
            b = j
            exit

print(a,b)

Buggy submission (verdict: Runtime Error):
X=int(input())
import numpy as np
t=int(X**(1/5))+10
a=[]
for i in range(t):
    a.append(i**5)

b=[]
for i in range(t):
    for j in range(i+1,t):
        if a[i]+a[j]==X:
            b.append([i,-j])
        if a[j]-a[i]==X:
            b.append([i,j])
        
print(b[0][0],b[0][1])

Buggy submission (verdict: Runtime Error):
X=int(input())
import numpy as np
t=int(X**(1/5))+10
i=-1
while  i < t:
    s=((i**5)+X)**(1/5)
    u=(X-(i**5))**(1/5)
    if s==int(s):
        print(i,int(s))
        break
    if u==int(u):
        print(i,int(-u))
        break
    i+=1
Problem p02698 (python)

Fixed submission:
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**6 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7
INT_MAX = 10**9
# MOD = 998244353


N = read_item()
vals = read_n_item()
graph = defaultdict(list)

for _ in range(N-1):
    u, v = read_n_item()
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)

ans = [0] * N
ans[0] = 1
dp = [vals[0]]


def dfs(cur, pre):
    ans[cur] = len(dp)

    for nxt in graph[cur]:
        if nxt == pre:
            continue
        i = bisect_left(dp, vals[nxt])
        if i < len(dp):
            temp = dp[i]
            dp[i] = vals[nxt]
            dfs(nxt, cur)
            dp[i] = temp
        else:
            dp.append(vals[nxt])
            dfs(nxt, cur)
            dp.pop()


dfs(0, -1)
print(*ans, sep='\n')

Buggy submission (verdict: Runtime Error):
import math
import sys
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from heapq import heapify, heappop, heappush
from itertools import chain, combinations, permutations, product
from typing import List, Dict

# import numpy as np

sys.setrecursionlimit(10**5 + 1)
input = sys.stdin.readline
write = sys.stdout.write


def read_item(cls=int):
    return cls(input())


def read_n_item(cls=int) -> list:
    return [cls(s) for s in input().split()]


def list2d(row, col, init_val=0) -> List[list]:
    return [[init_val] * col for _ in range(row)]


MOD = 10**9 + 7
# MOD = 998244353


N = read_item()
vals = read_n_item()
graph = defaultdict(list)

for _ in range(N-1):
    u, v = read_n_item()
    u -= 1
    v -= 1
    graph[u].append(v)
    graph[v].append(u)


ans = [0] * N
ans[0] = 1
dp = [float('inf')] * N
dp[0] = vals[0]


def dfs(v, pre):
    for child in graph[v]:
        if child == pre:
            continue
        i = bisect_left(dp, vals[child])
        ans[child] = i+1

        temp = dp[i]
        dp[i] = vals[child]
        dfs(child, v)
        dp[i] = temp

dfs(0, -1)
print(*ans, sep='\n')
Problem p02728 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import sys
from functools import reduce

MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(*args, mod=MOD):
    return reduce(lambda a, b: a * b % mod, args)


def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(dp[pre], dp[cur], fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        i = size[cur]
        temp = mul(ans[pre], f[n-i-1], fi[n-1], f[i], pow(dp[cur], m-2, m))
        ans[cur] = mul(f[n-1], temp, fi[n-i], dp[cur], fi[i-1])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

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

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import sys


MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(a, b, mod=MOD):
    return (a * b) % mod

@profile
def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(mul(dp[pre], dp[cur]), fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        ans[cur] = mul(ans[pre], size[cur]) // (n-size[cur])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

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

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()