Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import math

a, b = map(int, input().split())

n = math.gcd(a, b)

cd = []
for i in range(1, math.ceil(math.sqrt(n) + 1)):
    if n % i == 0:
        if n // i == i:
            cd.append(i)
        else:
            cd.append(i)
            cd.append(n // i)

cd.sort()

ans = 0
for i in range(len(cd)):
    for j in range(i + 1):
        if j == i:
            continue
        if cd[j] > 1 and cd[i] % cd[j] == 0:
            break
    else:
        ans += 1
print(ans)

Fixed submission:
import math
import fractions

a, b = map(int, input().split())

n = fractions.gcd(a, b)

cd = []
for i in range(1, math.ceil(math.sqrt(n) + 1)):
    if n % i == 0:
        if n // i == i:
            cd.append(i)
        else:
            cd.append(i)
            cd.append(n // i)

cd.sort()

ans = 0
for i in range(len(cd)):
    for j in range(i + 1):
        if j == i:
            continue
        if cd[j] > 1 and cd[i] % cd[j] == 0:
            break
    else:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

for i in range(m):
    value = a[-1] // 2
    del a[-1]
    bisect.insort(a, value)

print(sum(a))

Fixed submission:
import heapq


def neg_int(a):
    return -1 * int(a)


n, m = map(int, input().split())
a = sorted(list(map(neg_int, input().split())))
heapq.heapify(a)

for i in range(m):
    value = -1 * ((-1 * heapq.heappop(a)) // 2)
    heapq.heappush(a, value)

print(sum(a) * -1)

Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

for i in range(m):
    a[-1] = a[-1] // 2
    a.sort()

print(sum(a))

Fixed submission:
import heapq


def neg_int(a):
    return -1 * int(a)


n, m = map(int, input().split())
a = sorted(list(map(neg_int, input().split())))
heapq.heapify(a)

for i in range(m):
    value = -1 * ((-1 * heapq.heappop(a)) // 2)
    heapq.heappush(a, value)

print(sum(a) * -1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)


def main():
    n, q = map(int, input().split())

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

    operations = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        operations[p-1] += x

    counter = [-1] * n

    def calculate(p, i, v):
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                calculate(i, c, total)
        counter[i] = total

    calculate(-1, 0, 0)
    print(*counter)


main()

Fixed submission:
from collections import deque


def main():
    n, q = map(int, input().split())

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

    operations = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        operations[p-1] += x

    counter = [-1] * n
    d = deque([(-1, 0, 0)])
    while len(d) > 0:
        p, i, v = d.pop()
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                d.append((i, c, total))
        counter[i] = total

    print(*counter)


main()

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

n, q = map(int, input().split())

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

operations = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    operations[p-1] += x

counter = [-1] * n


def calculate(p, i, v):
    total = operations[i] + v
    for c in edges[i]:
        if c != p:
            calculate(i, c, total)
    counter[i] = total


calculate(-1, 0, 0)
print(' '.join(list(map(str, counter))))

Fixed submission:
from collections import deque


def main():
    n, q = map(int, input().split())

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

    operations = [0] * n
    for i in range(q):
        p, x = map(int, input().split())
        operations[p-1] += x

    counter = [-1] * n
    d = deque([(-1, 0, 0)])
    while len(d) > 0:
        p, i, v = d.pop()
        total = operations[i] + v
        for c in edges[i]:
            if c != p:
                d.append((i, c, total))
        counter[i] = total

    print(*counter)


main()
Buggy python submission (verdict: Time Limit Exceeded):
s = input().rstrip()

result = [0] * len(s)
for i in range(len(s)):
    if s[i] == 'R':
        for j in range(1, len(s)):
            if s[i+j] == 'L':
                break
        if j % 2 == 0:
            result[i+j] += 1
        else:
            result[i+j-1] += 1
    else:
        for j in range(1, len(s)):
            if s[i-j] == 'R':
                break
        if j % 2 == 0:
            result[i-j] += 1
        else:
            result[i-j+1] += 1
print(*result)

Fixed submission:
s = input().rstrip()

table = [0] * len(s)

start = 0
pre = 'R'
for i in range(1, len(s)):
    if pre != s[i]:
        if pre == 'R':
            for j in range(start, i):
                if (i - j) % 2 == 0:
                    table[i] += 1
                else:
                    table[i-1] += 1
        else:
            for j in range(start, i):
                if (i - j) % 2 == 0:
                    table[start-1] += 1
                else:
                    table[start] += 1

        pre = s[i]
        start = i

for j in range(start, len(s)):
    if (len(s) - j) % 2 == 0:
        table[start - 1] += 1
    else:
        table[start] += 1

print(*table)
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_left(c, a)
    if j == 0:
        c.insert(0, a)
    else:
        c[j-1] = a
print(len(c))

Fixed submission:
import bisect

n = int(input())

c = []
for i in range(n):
    a = int(input())
    j = bisect.bisect_right(c, -a)
    if j == len(c):
        c.append(-a)
    else:
        c[j] = -a
print(len(c))
Buggy python submission (verdict: Time Limit Exceeded):
from numpy.linalg import solve
n = int(input())
a = list(map(int, input().split()))

left = [[0] * n for _ in range(n)]
right = list(map(lambda x: x * 2, a))
for i in range(0, n):
    left[i][i] = 1
    left[i][(i+1)%n] = 1
b = solve(left, right)
print(*list(map(int, b)))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))

b = [0] * n
b[0] = sum(a) - 2 * sum(a[1::2])

for i in range(1, n):
    b[i] = 2 * a[i-1] - b[i-1]

print(*b)
Buggy python submission (verdict: Time Limit Exceeded):
l = input().rstrip()
n = len(l)
total = 0

mod = 10**9 + 7
c = 1
for i in range(n):
    if l[i] == '1':
        total += c * pow(3, n-i-1, mod)
        total %= mod
        c <<= 1
total += c
total %= mod
print(total)

Fixed submission:
l = input().rstrip()
n = len(l)

mod = 10**9 + 7
c = 1
d = 0
for i in range(n):
    d *= 3
    if l[i] == '1':
        d += c
        c <<= 1
    d %= mod
    c %= mod

print((c+d)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

d = []
for i in range(m):
    b, c = map(int, input().split())
    d.extend([c]*b)

d.sort(reverse=True)

for i in range(min(n, len(d))):
    if a[i] >= d[i]:
        break
    a[i] = d[i]

print(sum(a))

Fixed submission:
n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))

op = []
for i in range(m):
    b, c = map(int, input().split())
    op.append((c, b))

op.sort(reverse=True)

j = 0
k = 0

for i in range(n):
    if a[i] >= op[j][0]:
        break

    a[i] = op[j][0]
    k += 1

    if k >= op[j][1]:
        j += 1
        k = 0

    if j >= m:
        break

print(sum(a))
Buggy python submission (verdict: Runtime Error):
import networkx as nx

n, m = map(int, input().split())
g = nx.Graph()
g.add_nodes_from(range(1, n+1))
for i in range(m):
    x, y, z = map(int, input().split())
    g.add_edge(x, y)
print(nx.number_connected_components(g))

Fixed submission:
from collections import Counter


class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]
        self.size = [1 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x
            self.size[x] += self.size[y]

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

    def get_size(self, x):
        x = self.find(x)
        return self.size[x]


n, m = map(int, input().split())

uf = UnionFind(n)
for i in range(m):
    x, y, z = map(int, input().split())
    uf.union(x-1, y-1)

c = Counter([uf.find(i) for i in range(n)])
print(len(c))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

h, w = map(int, input().split())

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '#':
            d.append((i, j, 0))

while d:
    i, j, step = d.popleft()

    if op[i][j] != -1:
        continue
    else:
        op[i][j] = step

    if i > 0:
        d.append((i-1, j, step+1))
    if i < h-1:
        d.append((i+1, j, step+1))
    if j > 0:
        d.append((i, j-1, step+1))
    if j < w-1:
        d.append((i, j+1, step+1))

print(max([max(op[i]) for i in range(h)]))


Fixed submission:
from collections import deque

h, w = map(int, input().split())

d = deque()
op = [[-1] * w for i in range(h)]

for i in range(h):
    s = input().rstrip()
    for j in range(len(s)):
        if s[j] == '#':
            d.append((i, j, 0))
            op[i][j] = 0

while d:
    i, j, step = d.popleft()

    for i2, j2 in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
        if 0 <= i2 < h and 0 <= j2 < w:
            if op[i2][j2] == -1:
                d.append((i2, j2, step+1))
                op[i2][j2] = step + 1

print(max([max(op[i]) for i in range(h)]))
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

a, b, q = map(int, input().split())
s = sorted([int(input()) for _ in range(a)])
t = sorted([int(input()) for _ in range(b)])

for _ in range(q):
    x = int(input())
    s_i = bisect.bisect_left(s, x)
    t_i = bisect.bisect_left(t, x)

    s0, s1, t0, t1 = None, None, None, None
    ans = 10 ** 11
    if s_i > 0:
        s0 = x - s[s_i-1]
    if s_i < a:
        s1 = s[s_i] - x
    if t_i > 0:
        t0 = x - t[t_i-1]
    if t_i < b:
        t1 = t[t_i] - x

    if s0 is not None and t0 is not None:
        ans = min(ans, max(s0, t0))
    if s1 is not None and t1 is not None:
        ans = min(ans, max(s1, t1))
    if s0 is not None and t1 is not None:
        ans = min(ans, s0*2 + t1, t1*2 + s0)
    if s1 is not None and t0 is not None:
        ans = min(ans, s1*2 + t0, t0*2 + s1)

    print(ans)

Fixed submission:
import bisect
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines

a, b, q = map(int, input().split())
s = sorted([int(input()) for _ in range(a)])
t = sorted([int(input()) for _ in range(b)])

for _ in range(q):
    x = int(input())
    s_i = bisect.bisect_left(s, x)
    t_i = bisect.bisect_left(t, x)

    s0, s1, t0, t1 = None, None, None, None
    ans = 10 ** 11
    if s_i > 0:
        s0 = x - s[s_i-1]
    if s_i < a:
        s1 = s[s_i] - x
    if t_i > 0:
        t0 = x - t[t_i-1]
    if t_i < b:
        t1 = t[t_i] - x

    if s0 is not None and t0 is not None:
        ans = min(ans, max(s0, t0))
    if s1 is not None and t1 is not None:
        ans = min(ans, max(s1, t1))
    if s0 is not None and t1 is not None:
        ans = min(ans, s0*2 + t1, t1*2 + s0)
    if s1 is not None and t0 is not None:
        ans = min(ans, s1*2 + t0, t0*2 + s1)

    print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
from collections import Counter
n, m = map(int, input().split())
a = list(map(int, input().split()))

req_m = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [None] * (n+1)
dp[0] = Counter([])


for i in range(1, n+1):
    for j in a:
        if i >= req_m[j] and dp[i-req_m[j]] is not None:
            v = dp[i-req_m[j]] + Counter([j])
            if dp[i] is None:
                dp[i] = v
            else:
                if sum(dp[i].values()) < sum(v.values()):
                    dp[i] = v
                elif sum(dp[i].values()) == sum(v.values()):
                    if sorted(dp[i].elements(), reverse=True) < sorted(v.elements(), reverse=True):
                        dp[i] = v

print(''.join(map(str, sorted(dp[-1].elements(), reverse=True))))


Fixed submission:
import math
from collections import Counter
n, m = map(int, input().split())
a = list(map(int, input().split()))

if 9 in a and 6 in a:
    a.remove(6)
if 5 in a:
    if 2 in a:
        a.remove(2)
    if 3 in a:
        a.remove(3)
if 3 in a and 2 in a:
    a.remove(2)

req_m = [-1, 2, 5, 5, 4, 5, 6, 3, 7, 6]

dp = [None] * (n+1)
dp[0] = Counter([])

int_dp = [0] * (n+1)

for i in range(1, n+1):
    for j in a:
        if i >= req_m[j] and dp[i-req_m[j]] is not None:
            v = dp[i-req_m[j]] + Counter([j])
            if dp[i] is None:
                dp[i] = v
            else:
                if sum(dp[i].values()) < sum(v.values()):
                    dp[i] = v
                elif sum(dp[i].values()) == sum(v.values()):
                    if sorted(dp[i].elements(), reverse=True) < sorted(v.elements(), reverse=True):
                        dp[i] = v

print(''.join(map(str, sorted(dp[-1].elements(), reverse=True))))
Buggy python submission (verdict: Runtime Error):
import math

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

dp = [math.inf] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, n):
    dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]),
                dp[i-2] + abs(h[i] - h[i-2]))

print(dp[n-1])

Fixed submission:
n = int(input())
h = list(map(int, input().split()))

dp = [0] * n
dp[0] = 0
dp[1] = abs(h[1] - h[0])

for i in range(2, n):
    dp[i] = min(dp[i-1] + abs(h[i] - h[i-1]),
                dp[i-2] + abs(h[i] - h[i-2]))

print(dp[n-1])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

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

print(dp[-1])


Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

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

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n
dp[0] = 0

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

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

print(dp[n-1])


Fixed submission:
n, k = map(int, input().split())
h = list(map(int, input().split()))

dp = [0] * n

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

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
items = []
for _ in range(N):
    w, v = map(int, input().split())
    items.append({'w': w, 'v': v})

items.sort(key=lambda d: d['v'] / d['w'])

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    w = items[i - 1]['w']
    v = items[i - 1]['v']
    for j in range(1, W + 1):
        if w > j:
            dp[i][j] = dp[i][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)

print(dp[-1][-1])


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

import numpy as np
dp = np.zeros(W + 1, dtype='int64')

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)

print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())

MAX = 10**5 + 1
dp = [[10**13] * MAX for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MAX):
        if j < v:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)


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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[i][:v] = dp[i-1][:v]
    dp[i][v:] = np.minimum(dp[i-1][v:], dp[i-1][:-v] + w)

ans = np.where(dp[N] <= W)[0].max()

print(ans)

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())

import fractions
MAX = 10**5 + 1
dp = [[fractions.inf] * MAX for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MAX):
        if j < v:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)


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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[i][:v] = dp[i-1][:v]
    dp[i][v:] = np.minimum(dp[i-1][v:], dp[i-1][:-v] + w)

ans = np.where(dp[N] <= W)[0].max()

print(ans)

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())

import math
MAX = 10**5 + 1
dp = [[math.inf] * MAX for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    for j in range(MAX):
        if j < v:
            dp[i][j] = dp[i-1][j]
        else:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-v] + w)

ans = 0
for j in range(1, MAX):
    if dp[-1][j] <= W:
        ans = j

print(ans)


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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[i][:v] = dp[i-1][:v]
    dp[i][v:] = np.minimum(dp[i-1][v:], dp[i-1][:-v] + w)

ans = np.where(dp[N] <= W)[0].max()

print(ans)

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())

import numpy as np
dp = np.zeros(W + 1, dtype='int64')

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[w:W+1] = np.maximum(dp[w:W+1], dp[:W-w+1] + v)

print(dp[-1])


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

import numpy as np
MAX = 10**5 + 1
dp = [np.full(MAX, 10**13) for i in range(N + 1)]
dp[0][0] = 0

for i in range(1, N + 1):
    w, v = map(int, input().split())
    dp[i][:v] = dp[i-1][:v]
    dp[i][v:] = np.minimum(dp[i-1][v:], dp[i-1][:-v] + w)

ans = np.where(dp[N] <= W)[0].max()

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

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

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        dp[i][j] = a[i]
        return dp[i][j]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print(solve(0, len(a) - 1))


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[None] * len(a) for _ in a]

for i in range(len(a)-1, -1, -1):
    for j in range(i, len(a)):
        if i == j:
            dp[i][j] = a[i]
            continue

        dp[i][j] = max(a[j] - dp[i][j-1], a[i] - dp[i+1][j])

print(dp[0][len(a) - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**7)

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

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        return a[i]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print(solve(0, len(a) - 1))


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[None] * len(a) for _ in a]

for i in range(len(a)-1, -1, -1):
    for j in range(i, len(a)):
        if i == j:
            dp[i][j] = a[i]
            continue

        dp[i][j] = max(a[j] - dp[i][j-1], a[i] - dp[i+1][j])

print(dp[0][len(a) - 1])

Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

dp = [[None] * len(a) for _ in a]


def solve(i, j):
    if dp[i][j]:
        return dp[i][j]

    if i == j:
        return a[i]

    dp[i][j] = max(a[j] - solve(i, j-1), a[i] - solve(i+1, j))
    return dp[i][j]


print(solve(0, len(a) - 1))


Fixed submission:
n = int(input())
a = list(map(int, input().split()))

dp = [[None] * len(a) for _ in a]

for i in range(len(a)-1, -1, -1):
    for j in range(i, len(a)):
        if i == j:
            dp[i][j] = a[i]
            continue

        dp[i][j] = max(a[j] - dp[i][j-1], a[i] - dp[i+1][j])

print(dp[0][len(a) - 1])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**6)

n = int(input())

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

for i in range(n - 1):
    x, y = map(int, input().split())
    neighbor[y].append(x)
    neighbor[x].append(y)

mod = 10**9 + 7
dp = [[0] * 2 for _ in range(n + 1)]


def dfs(i, bw, p):
    if dp[i][bw] != 0:
        return dp[i][bw]

    dp[i][bw] = 1
    for j in neighbor[i]:
        if j == p:
            continue

        if bw == 0:  # black
            dp[i][0] = (dp[i][0] * dfs(j, 1, i)) % mod
        else:  # white
            dp[i][1] = (dp[i][1] * (dfs(j, 0, i) + dfs(j, 1, i))) % mod

    return dp[i][bw]


print((dfs(1, 0, 0) + dfs(1, 1, 0)) % mod)


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

n = int(input())

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

for i in range(n - 1):
    x, y = map(int, input().split())
    neighbor[y].append(x)
    neighbor[x].append(y)

mod = 10**9 + 7
dp = [[0] * 2 for _ in range(n + 1)]


def dfs(i, bw, p):
    if dp[i][bw] != 0:
        return dp[i][bw]

    dp[i][bw] = 1
    for j in neighbor[i]:
        if j == p:
            continue

        if bw == 0:  # black
            dp[i][0] = (dp[i][0] * dfs(j, 1, i)) % mod
        else:  # white
            dp[i][1] = (dp[i][1] * (dfs(j, 0, i) + dfs(j, 1, i))) % mod

    return dp[i][bw]


print((dfs(1, 0, 0) + dfs(1, 1, 0)) % mod)