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

Fixed submission:
# C

import bisect

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p_list = {int(x) for x in input().split()}
    q_list = {int(x) for x in range(102)}
    q_list = list(q_list - p_list)

    p = bisect.bisect_left(q_list, x)
    if p == 0:
        print(q_list[p])
    elif p == len(q_list):
        print(q_list[p-1])
    else:
        if abs(q_list[p-1] - x) <= abs(q_list[p] - x):
            print(q_list[p-1])
        else:
            print(q_list[p])

Buggy submission (verdict: Runtime Error):
# C

import bisect

x, n = map(int, input().split())
if n == 0:
    print(x)
else:
    p_list = {int(x) for x in input().split()}
    q_list = {int(x) for x in range(101)}
    q_list = list(q_list - p_list)

    p = bisect.bisect_left(q_list, x)
    if p == 0:
        print(q_list[p])
    else:
        if abs(q_list[p-1] - x) <= abs(q_list[p] - x):
            print(q_list[p-1])
        else:
            print(q_list[p])
Problem p02822 (python)

Fixed submission:
# 75

import sys
sys.setrecursionlimit(10**8)

MOD = 10**9+7
N = int(input())
g_l = [[] for i in range(N)]
check_l = [-1] * N
num_l = [0] * N
for i in range(N-1):
    ai, bi = map(int, input().split())
    g_l[ai-1].append(bi-1)
    g_l[bi-1].append(ai-1)


def dfs(n):
    d = 1
    if check_l[n] > 0:
        return num_l[n]
    check_l[n] = 1
    for next_n in g_l[n]:
        d += dfs(next_n)
    num_l[n] = d
    return d


def modinv(a):
    # calc : (a**(-1)) %MOD
    return pow(a, MOD-2, MOD)


def solve():
    dfs(0)
    pow_l = [None]*(N+1)
    pow_l[0] = 1
    for i in range(1, N+1):
        pow_l[i] = (pow_l[i-1] * 2) % MOD

    ans = 0
    # for i in range(1, N):
    #     ans += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
    # ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
    # ans -= N/2  # 黒点の期待値を引く
    for i in range(1, N):
        ans = (ans + (pow_l[num_l[i]]-1) *
               (pow_l[N-num_l[i]]-1) % MOD) % MOD
    ans = (ans + (pow_l[N] - 1) - (N * pow_l[N-1]) % MOD) % MOD
    y = ans
    x = pow(2, N, MOD)

    z = (y * modinv(x)) % MOD

    print(z)


solve()

Buggy submission (verdict: Runtime Error):
# 75

from fractions import Fraction

MOD = 10**9+7
N = int(input())
g_l = [[] for i in range(N)]
check_l = [-1] * N
num_l = [0] * N
for i in range(N-1):
    ai, bi = map(int, input().split())
    g_l[ai-1].append(bi-1)
    g_l[bi-1].append(ai-1)


def dfs(n):
    d = 1
    if check_l[n] > 0:
        return num_l[n]
    check_l[n] = 1
    for next_n in g_l[n]:
        d += dfs(next_n)
    num_l[n] = d
    return d


def modpow(a, n):
    # calc : (a**n)%MOD
    ret = 1
    while n > 0:
        if n & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        n >>= 1
    return ret


def modinv(a):
    # calc : (a**(-1)) %MOD
    return modpow(a, MOD-2)


dfs(0)

ans = 0
for i in range(1, N):
    ans += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
ans -= N/2  # 黒点の期待値を引く

tmp = Fraction(ans)
x = tmp.denominator
y = tmp.numerator

z = (modinv(x) * y) % MOD

print(z)
Problem p03161 (python)

Fixed submission:
# B Frog 2

n, k = map(int, input().split())
h_list = [int(x) for x in input().split()]

dp = [float('Inf')] * n
dp[0] = 0

for i in range(n):
    for j in range(1,k+1,1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i], dp[i-j] + abs(h_list[i-j]-h_list[i]))

        
print(dp[n-1])

Buggy submission (verdict: Runtime Error):
# B Frog 2

n, k = map(int, input().split())
h_list = [int(x) for x in input().split()]

dp = [float('Inf')] * 2*n
dp[0] = 0

for i in range(n):
    for j in range(1,k+1,1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h_list[i+j]-h_list[i]))

        
print(dp[n-1])

Buggy submission (verdict: Runtime Error):
# B Frog 2

n, k = map(int, input().split())
h_list = [int(x) for x in input().split()]

dp = [float('Inf')] * n
dp[0] = 0

for i in range(n):
    for j in range(1,k+1,1):
        dp[i+j] = min(dp[i+j], dp[i] + abs(h_list[i+j]-h_list[i]))

        
print(dp[n-1])

Buggy submission (verdict: Runtime Error):
# B Frog 2

n, k = map(int, input().split())
h_list = [int(x) for x in input().split()]

dp = [float('Inf')] * n
dp[0] = 0

for i in range(1,n,1):
    _step = max(0,i-k)
    for j in range(_step,i,1):
        dp[i] = min(dp[i], dp[j] + abs(h_list[i]-h_list[j]))

print(dp[n])
Problem p03164 (python)

Fixed submission:
# E Knapsack 2

from collections import deque

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
for i in range(n+1):
    dp[i][0] = 0

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(MAX_V):
        if j-_v < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = min(dp[i][j], dp[i][j-_v]+_w)

ans = 0
for i in range(MAX_V):
    if dp[n][i] <= w:
        ans = i
print(ans)

Buggy submission (verdict: Runtime Error):
# E Knapsack 2

import sys

sys.setrecursionlimit(10**8)

MAX_V = 10**5+1
n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("Inf")] * (MAX_V) for _ in range(n+1)]
dp[0][0] = 0
memo = [[False] * (MAX_V) for _ in range(n+1)]
memo[0] = [True] * (MAX_V)

def dp_solve(i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_v < 0:
        _ret = dp_solve(i-1, j)
    else:
        _ret = min(dp_solve(i-1, j), dp_solve(i-1, j-_v) + _w)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(n, w))

Buggy submission (verdict: Runtime Error):
# D Knapsack 1
import copy

n, w = map(int, input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)] # n*2

dp = [float('-Inf')] * (w+2)
dp[0] = 0
buy_list = [[False] * n for j in range(w+2)] # (w+2)*n

for i in range(w):
    for j in range(n):
        if buy_list[i][j]:
            continue
        _w = wv_list[j][0]
        _v = wv_list[j][1]
        if i+_w > w:
            _w = w - i + 1
        if dp[i+_w] < dp[i]+_v:
            dp[i+_w] = dp[i]+_v
            buy_list[i+_w] = copy.deepcopy(buy_list[i])
            buy_list[i+_w][j] = True
            
print(max(dp[:w+1]))

Buggy submission (verdict: Runtime Error):
# D Knapsack 1


n, w = map(int,input().split())
wv_list = [[int(x) for x in input().split()] for y in range(n)]

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)
memo = [[False] * (w+1) for _ in range(n+1)]
memo[0] = [True] * (w+1)

def dp_solve(dp, wv_list, i, j):
    if memo[i][j]:
        return dp[i][j]
    _w,_v = wv_list[i-1]
    _ret = 0
    if j-_w < 0:
        _ret = dp_solve(dp, wv_list, i-1, j)
    else:
        _ret = max(dp_solve(dp, wv_list, i-1, j), dp_solve(dp, wv_list, i-1, j-_w) + _v)
    dp[i][j] = _ret
    memo[i][j] = True
    return _ret

print(dp_solve(dp, wv_list, n, w))

Buggy submission (verdict: Runtime Error):
# D Knapsack 1

from collections import deque

n, w = map(int,input().split())
wv_list = deque([[int(x) for x in input().split()] for y in range(n)])

dp = [[float("-Inf")] * (w+1) for _ in range(n+1)]
dp[0] = [0]*(w+1)

for i in range(n):
    _w,_v = wv_list.popleft()
    for j in range(w+1):
        if j-_w < 0:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-_w]+_v)

print(dp[n][w])
Problem p03611 (python)

Fixed submission:
# ABC072
# C
# Together
import itertools

n = int(input())
a = [int(i) for i in input().split()]

a.sort()
gr = itertools.groupby(a)
hoge_list = [0]*100001
ans = 0

for key, group in gr:
    hoge_list[key] = len(list(group))

for i in range(1,100000,1):
    _tmp = hoge_list[i-1] + hoge_list[i] + hoge_list[i+1]
    if ans < _tmp:
        ans = _tmp

print(ans)

Buggy submission (verdict: Runtime Error):
# ABC072
# C
# Together
import itertools

n = int(input())
a = [int(i) for i in input().split()]

a.sort()
gr = itertools.groupby(a)
hoge_list = [0]*10001
ans = 0

for key, group in gr:
    hoge_list[key] = len(list(group))

for i in range(1,10000,1):
    _tmp = hoge_list[i-1] + hoge_list[i] + hoge_list[i+1]
    if ans < _tmp:
        ans = _tmp

print(ans)

Buggy submission (verdict: Runtime Error):
# ABC072
# C
# Together
import itertools

n = int(input())
a = [int(i) for i in input().split()]

a.sort()
gr = itertools.groupby(a)
hoge_list = [0]*10001
ans = 0

for key, group in gr:
    hoge_list[key] = len(list(group))

for i in range(1000):
    _tmp = hoge_list[i-1] + hoge_list[i] + hoge_list[i+1]
    if ans < _tmp:
        ans = _tmp

print(ans)
Problem p03695 (python)

Fixed submission:
# ABC064
# C
# Colorful Leaderboard

n = int(input())
a_list = list(map(int, input().split()))

color_list = [0]*8
over = 0
for i in range(n):
    _ = a_list[i] // 400
    if _ < 8:
        color_list[_] = 1
    else:
        over += 1

_tmp = sum(color_list)
if _tmp == 0:
    print("1 %d"%over)
else:
    print("%d %d"%(_tmp, _tmp+over))

Buggy submission (verdict: Runtime Error):
# ABC064
# C
# Colorful Leaderboard

n = int(input())
a_list = list(map(int, input().split()))

color_list = [0]*8
over = 0
for i in range(n):
    _ = a_list[i] // 400
    if _ < 8:
        color_list[_] = 1
    else:
        over += 1

_tmp = sum(color_list)
if _tmp == 0:
    print("1 %d"%_over)
else:
    print("%d %d"%(_tmp, _tmp+over))

Buggy submission (verdict: Runtime Error):
# ABC064
# C
# Colorful Leaderboard

n = int(input())
a_list = list(map(int, input().split()))

color_list = [0]*8
over = 0
for i in range(n):
    _ = a_list[i] // 400
    if _ < 8:
        color_list[i] = 1
    else:
        over += 1

_tmp = sum(color_list)
print("%d %d"%(_tmp, _tmp+over))
Problem p02684 (python)

Fixed submission:
def solve(N, K, A):
    idx = [-1 for _ in range(len(A))]
    now = 0
    period = 0
    bias = 0
    tmp = []
    found = False
    i = 0
    while not found:
        tmp.append(now+1)
        if idx[now] == -1:
            idx[now] = i
        else:
            period = i - idx[now]
            cycle = tmp[-period-1:-1]
            bias = i - period
            break
        now = A[now]-1
        i += 1

    if K <= bias:
        now = 0
        for _ in range(K):
            now = A[now] - 1
        print(now + 1)
    else:
        K -= bias
        K = K % period
        print(cycle[K])

if __name__=="__main__":
    N,K = [int(a) for a in input().split()]
    A = [int(a) for a in input().split()]
    solve(N, K, A)

Buggy submission (verdict: Runtime Error):
N,K = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

idx = [-1 for _ in range(len(A))]
now = 0
period = 0
bias = 0
tmp = []
for i in range(K+1):
    tmp.append(now+1)
    if idx[now] == -1:
        idx[now] = i
    else:
        period = i - idx[now]
        cycle = tmp[-period-1:-1]
        bias = i - period
        break
    now = A[now]-1

if K <= bias:
    now = 0
    for _ in range(K):
        now = A[now] - 1
    print(now + 1)
else:
    K -= bias
    K = K % period
    print(cycle[K])

Buggy submission (verdict: Runtime Error):
N,K = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

idx = [-1 for _ in range(len(A))]
now = 0
period = 0
bias = 0
tmp = []
for i in range(K):
    tmp.append(now+1)
    if idx[now] == -1:
        idx[now] = i
    else:
        period = i - idx[now]
        cycle = tmp[-period-1:-1]
        bias = i - period
        break
    now = A[now]-1

if K <= bias:
    now = 0
    for _ in range(K):
        now = A[now] - 1
    print(now + 1)
else:
    K -= bias
    K = K % period
    print(cycle[K])
Problem p02675 (python)

Fixed submission:
last = int(input()[-1])
     
if last in [2,4,5,7,9]:
  print('hon')
elif last in [0,1,6,8]:
  print('pon')
else:
  print('bon')

Buggy submission (verdict: Runtime Error):
import sys
     
data = []
     
for l in sys.stdin:
    data.append(str(l))
       
last = int(data[0][-1])
     
if last in [2,4,5,7,9]:
  print('hon')
elif last in [0,1,6,8]:
  print('pon')
else:
  print('hon')

Buggy submission (verdict: Runtime Error):
import sys
     
data = []
     
for l in sys.stdin:
    data.append(str(l))
       
last = int(data[0][-1])
     
if last in [2,4,5,7,9]:
  print('hon')
elif last in [0,1,6,8]:
  print('pon')
else:
  print('hon')

Buggy submission (verdict: Runtime Error):
import sys

data = []
 
for l in sys.stdin:
    data.append(str(l))
    
last = int(data[0][-1])

if last in [2,4,5,7,9]:
  print('hon')
elif last in [0,1,6,8]:
  print('pon')
else:
  print('hon')

Buggy submission (verdict: Runtime Error):
import numpy as np
import sys

data = []

for l in sys.stdin:
    data.append(l)
    
last = int(data[0][-1])

if last in [2,4,5,7,9]:
  print('hon')
elif last in [0,1,6,8]:
  print('pon')
else:
  print('hon')
Problem p02585 (python)

Fixed submission:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -10**18

for i in range(N):
    now = i
    visit = [False]*N
    visit[now] = True
    l = []
    
    for _ in range(N+10):
        nex = P[now]-1
        l.append(C[nex])
        
        if visit[nex]:
            break
        
        visit[nex] = True
        now = nex
    
    s = sum(l)
    now = 0
    
    for i in range(min(K, len(l))):
        now += l[i]
        ans = max(ans, now+(K-i-1)//len(l)*max(0, s))
    
print(ans)

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

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -10**18
P = list(map(lambda x: x-1, P))

for i in range(N):
    visit = [False]*N
    now = i
    l = []
    visit[now] = True
    
    for j in range(N+10):
        nex = P[now]
        l.append(C[nex])
        
        if visit[nex]:
            break
        
        visit[nex] = True
        now = nex
    
    su = sum(l)
    
    if su>=0:
        if K>=len(l):
            now = su*(K//len(l))
            rem = K%len(l)
            ans = max(ans, now)
        
            for j in range(rem):
                now += l[j]
                ans = max(ans, now)
                
            now = l[0]
            ans = max(ans, now)
            
            for j in range(1, len(l)):
                now += l[i]
                ans = max(ans, now)
        else:
            now = l[0]
            ans = max(ans, now)
            
            for j in range(1, K):
                now += l[j]
                ans = max(ans, now)
    else:
        now = l[0]
        ans = max(ans, now)
        
        if K<len(l):
            for j in range(1, K):
                now += l[j]
                ans = max(ans, now)
        else:
            for j in range(1, len(l)):
                now += l[j];
                ans = max(ans, now)

print(ans)
Problem p02599 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import *

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*N

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)
Problem p02609 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import *

def f(i):
    if C==1:
        if i==mark:
            return 0
        else:
            if X[i]=='0':
                nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
            else:
                nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
            res = 1
    
            while nex>0:
                pc = 0
        
                for i in range(20):
                    if (nex>>i)&1:
                        pc += 1
        
                nex %= pc
                res += 1
    
            return res
        
            
    if X[i]=='0':
        nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
    else:
        nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
    res = 1
    
    while nex>0:
        pc = 0
        
        for i in range(20):
            if (nex>>i)&1:
                pc += 1
        
        nex %= pc
        res += 1
    
    return res

N = int(input())
X = list(input()[:-1])

if X=='0'*N:
    for i in range(N):
        print(1)
    exit()

C = X.count('1')

for i in range(N):
    if X[i]=='1':
        mark = i
    
p = 0

for Xi in X:
    if Xi=='1':
        p += 1

d = defaultdict(int)

if C==1:
    for i in [p, p+1]:
        for j in range(N):
            if X[j]=='1':
                d[i] += pow(2, N-1-j, i)
else:
    for i in [p-1, p, p+1]:
        for j in range(N):
            if X[j]=='1':
                d[i] += pow(2, N-1-j, i)

for i in range(N):
    print(f(i))

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import *

def f(i):
    if X[i]=='0':
        nex = (d[p+1]+pow(2, N-1-i, p+1))%(p+1)
    elif X[i]=='1':
        nex = (d[p-1]-pow(2, N-1-i, p-1))%(p-1)
    
    res = 1
    
    while nex>0:
        pc = 0
        
        for i in range(20):
            if (nex>>i)&1:
                pc += 1
        
        nex %= pc
        res += 1
    
    return res

N = int(input())
X = input()[:-1]

if X=='0'*N:
    for i in range(N):
        print(1)
    exit()
    
p = 0

for Xi in X:
    if Xi=='1':
        p += 1

d = defaultdict(int)

for i in [p-1, p, p+1]:
    for j in range(N):
        if X[j]=='1':
            d[i] += pow(2, N-1-j, i)

for i in range(N):
    print(f(i))
Problem p02632 (python)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import Counter

MAX = 2*10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

K = int(input())
S = input()[:-1]
N = len(S)
ans = 0

for i in range(K+1):
    ans += C(N+K-i-1, N-1)*pow(26, i, MOD)*pow(25, K-i, MOD)
    ans %= MOD
    
print(ans)

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import Counter

MAX = 10**6+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

K = int(input())
S = input()[:-1]
N = len(S)
ans = 0

for i in range(K+1):
    ans += C(N+K-i-1, N-1)*pow(26, i, MOD)*pow(25, K-i, MOD)
    ans %= MOD
    
print(ans)
Problem p02698 (python)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2*10**5+100)
from bisect import *

def dfs(v, pv):
    j = bisect_left(dp, a[v])
    prev = dp[j]
    dp[j] = a[v]
    ans[v] = bisect_left(dp, 10**18)-1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs(nv, v)
    
    dp[j] = prev

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

for _ in range(N-1):
    u, v = map(int, input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

dp = [10**18]*(N+1)
dp[0] = -10**18
ans = [-1]*N
dfs(0, -1)

for ans_i in ans:
    print(ans_i)

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

def dfs(v, pv):
    j = bisect_left(dp, a[v])
    prev = dp[j]
    dp[j] = a[v]
    ans[v] = bisect_left(dp, 10**18)-1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs(nv, v)
    
    dp[j] = prev

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

for _ in range(N-1):
    u, v = map(int, input().split())
    G[u-1].append(v-1)
    G[v-1].append(u-1)

dp = [10**18]*(N+1)
dp[0] = -10**18
ans = [-1]*N
dfs(0, -1)

for ans_i in ans:
    print(ans_i)
Problem p02716 (python)

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

if N%2==0:
    dp = [[0]*2 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
    
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    dp = [[0]*3 for _ in range(N)]
    dp[0][0] = A[0]
    dp[1][1] = A[1]
    dp[2][2] = A[2]
    
    for i in range(2, N):
        if i==2:
            dp[i][0] = dp[i-2][0]+A[i]
        elif i==3:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-2][1]+A[i], dp[i-3][0]+A[i])
        else:
            dp[i][0] = dp[i-2][0]+A[i]
            dp[i][1] = max(dp[i-3][0]+A[i], dp[i-2][1]+A[i])
            dp[i][2] = max(dp[i-4][0]+A[i], dp[i-3][1]+A[i], dp[i-2][2]+A[i])
    
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))

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

N = int(input())
A = list(map(int, input().split()))
dp = [[-10**18]*3 for _ in range(N)]
dp[0][0] = A[0]
dp[1][1] = A[1]
dp[2][2] = A[2]

for i in range(2, N):
    dp[i][0] = dp[i-2][0]+A[i]
    dp[i][1] = max(dp[i][1], dp[i-2][1]+A[i])
    
    if i>=3:
        dp[i][1] = max(dp[i][1], dp[i-3][0]+A[i])
    
    dp[i][2] = max(dp[i][2], dp[i-2][2]+A[i])
    
    if i>=3:
        dp[i][2] = max(dp[i][2], dp[i-3][1]+A[i])
    
    if i>=4:
        dp[i][2] = max(dp[i][2], dp[i-4][0]+A[i])

if N%2==0:
    print(max(dp[N-2][0], dp[N-1][1]))
else:
    print(max(dp[N-3][0], dp[N-2][1], dp[N-1][2]))