Problem:


Score : 700 points

Problem Statement

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N.
Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i.
Now, process the following query Q times:

Given are a vertex v of the tree and a positive integer L.
  Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L.
  Find the maximum possible total value of the chosen items.

Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query.
Then, Input is given from Standard Input in the following format:

N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q

Output

For each integer i from 1 through Q,
the i-th line should contain the response to the i-th query.

Sample Input 1

3
1 2
2 3
3 4
3
1 1
2 5
3 5

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with (V, W)=(1,2). Since L = 1, we cannot actually choose it, so our response should be 0.

In the second query, we are given two choices: the items with (V, W)=(1,2) and (V, W)=(2,3). Since L = 5, we can choose both of them, so our response should be 3.

Sample Input 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

Sample Output 2

256
255
250
247
255
259
223
253



Sample input:
3
1 2
2 3
3 4
3
1 1
2 5
3 5


Sample output:
0
3
3

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = tuple(data[:2*n:2])
W = tuple(data[1:2*n:2])
q = data[2*n]
v = tuple(data[2*n+1::2])
L = tuple(data[2*n+2::2])

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(12, n.bit_length()-1)
max_bef = 2**b_len

bef = [ [] for _ in range(2**b_len)]
bef[1] = [(0,0),(W[0],V[0])]

for i in range(2,2**b_len):
    iw,iv = W[i-1],V[i-1]
    bef[i] = bef[i//2][::]
    for jw,jv in bef[i//2]:
        bef[i].append((iw+jw,iv+jv))

bef_max = [ [0]*(10**5 + 1) for _ in range(max_bef)]

for i in range(1,max_bef):
    for jw,jv in bef[i]:
        bef_max[i][jw] = max(bef_max[i][jw], jv)

    for j in range(1,10**5+1):
        bef_max[i][j] = max(bef_max[i][j],bef_max[i][j-1])

Submission status: Runtime Error

Solution code:
import sys,bisect
input=sys.stdin.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(100001)] for i in range(2**10)]
for i in range(vw[1][1],100001):
    dp[1][i]=vw[1][0]
MAX=min(2**10,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(w):
        dp[i][j]=dp[i//2][j]
    for j in range(w,100001):
        dp[i][j]=max(dp[i//2][j],dp[i//2][j-w]+v)

for i in range(int(input())):
    v,L=map(int,input().split())
    if 2**10>v:
        print(dp[v][L])
    else:
        t=[]
        while v>=2**10:
            t.append(vw[v])
            v//=2
        n=len(t)
        temp=[[0,0] for i in range(2**n)]
        for i in range(1,2**n):
            m=i.bit_length()
            temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
            temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
        ans=0
        for i in range(2**n):
            ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]]*(L>=temp[i][1]))
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = tuple(data[:2*n:2])
W = tuple(data[1:2*n:2])
q = data[2*n]
v = tuple(data[2*n+1::2])
L = tuple(data[2*n+2::2])

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(12, n.bit_length()-1)
max_bef = 2**b_len

bef = [ [] for _ in range(2**b_len)]
bef[1] = [(0,0),(W[0],V[0])]

for i in range(2,2**b_len):
    iw,iv = W[i-1],V[i-1]
    bef[i] = bef[i//2][::]
    for jw,jv in bef[i//2]:
        bef[i].append((iw+jw,iv+jv))

bef_max = [ [0]*(10**5 + 1) for _ in range(max_bef)]

for i in range(1,max_bef):
    for jw,jv in bef[i]:
        bef_max[i][jw] = max(bef_max[i][jw], jv)

    for j in range(1,10**5+1):
        bef_max[i][j] = max(bef_max[i][j],bef_max[i][j-1])

ans = []
for vi,Li in zip(v,L):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    par = vi
    while(par>= max_bef):
        par //= 2

    aft = [(0,0)]
    x = vi
    max_ans = bef_max[par][Li]
    while(x >= max_bef):
        xw,xv = W[x-1],V[x-1]
        aft2 = []
        for jw,jv in aft:
            jw += xw
            jv += xv
            lim_w = Li - jw
            if(lim_w < 0):
                continue
            aft2.append((jw,jv))
            max_ans = max(max_ans, bef_max[par][lim_w]+jv)
        x //= 2
        aft = aft + aft2

    ans.append(max_ans)

print('\n'.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
import sys,bisect
input=sys.stdin.readline

N=int(input())
vw=[(-1,-1)]
for i in range(N):
    vw.append(tuple(map(int,input().split())))

dp=[[0 for i in range(1001)] for i in range(2**10)]
for i in range(vw[1][1],1001):
    dp[1][i]=vw[1][0]
MAX=min(2**10,N+1)
for i in range(2,MAX):
    v,w=vw[i]
    for j in range(w):
        dp[i][j]=dp[i//2][j]
    for j in range(w,1001):
        dp[i][j]=max(dp[i//2][j],dp[i//2][j-w]+v)

for i in range(int(input())):
    v,L=map(int,input().split())
    if 2**10>v:
        print(dp[v][L])
    else:
        t=[]
        while v>=2**10:
            t.append(vw[v])
            v//=2
        n=len(t)
        temp=[[0,0] for i in range(2**n)]
        for i in range(1,2**n):
            m=i.bit_length()
            temp[i][0]=temp[i-2**(m-1)][0]+t[m-1][0]
            temp[i][1]=temp[i-2**(m-1)][1]+t[m-1][1]
        ans=0
        for i in range(2**n):
            ans=max(ans,temp[i][0]+dp[v][L-temp[i][1]]*(L>=temp[i][1]))
        print(ans)

Submission status: Runtime Error

Solution code:
def main():  
  N = int(input())
  VW = [list(map(int,input().split())) for _ in range(N)]
  Q = int(input())
  vL = [list(map(int,input().split())) for _ in range(Q)]
  M = 0
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = dict()
  for i in range(2**K):
    for j in range(M+1):
      Ddp[i] = {}
      Ddp[i][j] = 0

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Runtime Error

Solution code:
def main():  
  N = int(input())
  VW = [list(map(int,input().split())) for _ in range(N)]
  Q = int(input())
  vL = [list(map(int,input().split())) for _ in range(Q)]
  M = 0
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = dict{}
  for i in range(2**K):
    for j in range(M+1):
      Ddp[i] = {}
      Ddp[i][j] = 0

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Runtime Error

Solution code:
def main():  
  N = int(input())
  VW = [list(map(int,input().split())) for _ in range(N)]
  Q = int(input())
  vL = [list(map(int,input().split())) for _ in range(Q)]
  M = 0
  import math
  from collections import deque
  for q in range(Q):
    x = vL[q][1]
    if x>M:
      M = x

  D = int(math.log2(N)) + 1
  K = D//2
  Ddp = dict{}
  for i in range(2**K):
    Ddp[i] = [0]*(M+1)

  for q in range(Q):
    v,L = vL[q]
    if v<=2**K - 1:
      print(Ddp[v][L])
      continue
    
main()

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
data = list(map(int,read().split()))

V = tuple(data[:2*n:2])
W = tuple(data[1:2*n:2])
q = data[2*n]
v = tuple(data[2*n+1::2])
L = tuple(data[2*n+2::2])

if(n==1):
    ans = []
    for i,j in zip(v,L):
        if(W[i-1] <= j):
            ans.append(V[0])
        else:
            ans.append(0)
    print('\n'.join(map(str,ans)))
    exit()

# 前処理　最大2**9まで前計算
b_len = min(9, n.bit_length()-1)
max_bef = 2**b_len
bef = [ [0]*(10**5 + 1) for _ in range(max_bef)]

for i in range(1,max_bef):
    iw,iv = W[i-1],V[i-1]
    par = i//2
    for j in range(1,10**5+1):
        if(j>=iw):
            bef[i][j] = max(bef[par][j] , bef[par][j-iw]+iv)
        else:
            bef[i][j] = bef[par][j]

ans = []
for vi,Li in zip(v,L):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    max_ans = 0
    aft = [(0,0)]
    x = vi
    while(x >= max_bef):
        xw,xv = W[x-1],V[x-1]
        x //= 2
        if(x >= max_bef):
            for jw,jv in aft:
                lim_w = Li - (jw+xw)
                if(lim_w >= 0):
                    max_ans = max(max_ans, bef[x][lim_w]+jv+xw)
            break

        aft2 = []
        for jw,jv in aft:
            jw += xw
            jv += xv
            lim_w = Li - (jw)
            if(lim_w >= 0):
                max_ans = max(max_ans, bef[x][lim_w]+jv)
                aft2.append((jw,jv))

        aft = aft + aft2
    max_ans = max(max_ans, bef[x][lim_w])

    ans.append(max_ans)

print('\n'.join(map(str,ans)))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2)]
    for i in range(1, (1 << len(dp[n]) // 2)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        dv = d[V]
        for v, w in lis2:
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys


def main():
    input = sys.stdin.readline

    n = int(input())
    items = [tuple(map(int, input().split())) for _ in range(n)]

    L_MAX = 10**5
    D_TH = 10
    V_MAX = 1 << D_TH
    dp = [[0] * (L_MAX + 1) for _ in range(V_MAX + 1)]

    for i, (val, w) in enumerate(items[:V_MAX]):
        for j in range(L_MAX):
            i1 = i + 1
            i0 = (i + 1) // 2
            if j < w:
                dp[i1][j] = dp[i0][j]
            else:
                dp[i1][j] = max(dp[i0][j], dp[i0][j - w] + val)

    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        v -= 1

        if v + 1 <= V_MAX:
            ans = dp[v + 1][l]
        else:
            items_sub = [items[v]]
            while v > V_MAX:
                v = (v - 1) // 2
                items_sub.append(items[v])

            ans = 0
            for bit in range(1 << len(items_sub)):
                s_val = s_w = 0
                for i, (val, w) in enumerate(items_sub):
                    if (bit >> i) & 1:
                        s_val += val
                        s_w += w
                if s_w <= l:
                    ans = max(ans, dp[l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << n.bit_length() - 1):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        dpi = dp[i]
        for j in t:
            if j <= n:
                v, w = vw[j - 1]
                dpi.append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2 + 1)]
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
    return  
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        dv = d[V]
        for v, w in lis2:
            if L - w < 0: continue
            if dv[L - w] + v > ans:
                ans = dv[L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << (n.bit_length() - 1)):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        for j in list(t):
            if j <= n:
                v, w = vw[j - 1]
                dp[i].append((v, w))
    M = 10 ** 5 + 1
    d = [[0] * M for _ in range(1 << len(dp[n]) // 2 + 1)]
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        di = d[i]
        for v, w in tmp:
            if di[w] < v:
                di[w] = v
        for j in range(M - 1):
            if di[j + 1] < di[j]:
                di[j + 1] = di[j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        for v, w in lis2:
            if L - w < 0: continue
            if d[V][L - w] + v > ans:
                ans = d[V][L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << (n.bit_length() - 1)):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        for j in list(t):
            if j <= n:
                v, w = vw[j - 1]
                dp[i].append((v, w))
    d = defaultdict(list)
    M = 10 ** 5 + 1
    d[0] = [0] * M
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        d[i] = [0] * M
        for v, w in tmp:
            if d[i][w] < v:
                d[i][w] = v
        for j in range(M - 1):
            if d[i][j + 1] < d[i][j]:
                d[i][j + 1] = d[i][j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        V = V >> n2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        for v, w in lis2:
            if L - w < 0: continue
            if d[V][L - w] + v > ans:
                ans = d[V][L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
dame = 10**5+1
point = [[0 for weight in range(dame)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大

for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, max(W + maW[(k//2)]+1, dame)):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(point[v][min(L, maW[v])])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    vw = LIR(n)
    dp = [[i] for i in range(1 << n.bit_length())]
    for i in range(1, 1 << (n.bit_length() - 1)):
        dp[2 * i] = dp[i] + dp[2 * i]
        dp[2 * i + 1] = dp[i] + dp[2 * i + 1]
    for i in range(1, n + 1):
        t = dp[i]
        dp[i] = []
        for j in list(t):
            if j <= n:
                v, w = vw[j - 1]
                dp[i].append((v, w))
    d = defaultdict(list)
    M = 10 ** 5 + 1
    for i in range(1, (1 << len(dp[n]) // 2 + 1)):
        tmp = [(0, 0)]
        for v, w in dp[i]:
            tmp += [(vi + v, wi + w) for vi, wi in tmp]
        d[i] = [0] * M
        for v, w in tmp:
            if d[i][w] < v:
                d[i][w] = v
        for j in range(M - 1):
            if d[i][j + 1] < d[i][j]:
                d[i][j + 1] = d[i][j] 
                
    for _ in range(II()):
        V, L = LI()
        t = dp[V]
        n1 = len(t) // 2
        n2 = len(t) - n1
        vw2 = t[n1:]
        for _ in range(n2):
            V //= 2
        lis2 = [(0, 0)]
        for v, w in vw2:
            lis2 += [(vi + v, wi + w) for vi, wi in lis2]
        ans = 0
        for v, w in lis2:
            if L - w < 0: continue
            if d[V][L - w] + v > ans:
                ans = d[V][L - w] + v
        print(ans)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
N = int(input())
dame = 10**5+1
point = [[0 for weight in range(dame)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大

for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, max(W + maW[(k//2)]+1, dame)):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(maW[k//2], W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(point[v][min(L, maW[v])])

Submission status: Runtime Error

Solution code:
N = int(input())
point = [[0 for weight in range(10**5+1)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大
dame = 10**5+1
for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, max(W + maW[(k//2)]+1, dame)):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(maW[k//2], W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(max(point[v][:L+1]))

Submission status: Runtime Error

Solution code:
N = int(input())
point = [[0 for weight in range(10**5+1)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大
for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, W + maW[(k//2)]+1):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(maW[k//2], W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(max(point[v][:L+1]))

Submission status: Runtime Error

Solution code:
N = int(input())
point = [[0 for weight in range(10)] for tree in range(N+1)]
maW = [0 for k in range(N+1)] #枝の重さの最大
for k in range(1,N+1):
    V, W = map(int, input().split())
    for n in range(W, W + maW[(k//2)]+1):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(maW[k//2], W):
        point[k][j] = point[k//2][j]
    maW[k] = maW[k//2] + W

   

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(max(point[v][:L+1]))

Submission status: Runtime Error

Solution code:
N = int(input())
M = 10**5
VW = [(0, 0)] + [tuple(map(int, input().split())) for i in range(N)]

dp = [[0] * (M+1) for i in range(512)]
for i in range(1, 512):
  if i > N:
    break
  v, w = VW[i]
  par = i//2
  for wi in range(M+1):
    if wi < w:
      dp[i][wi] = dp[par][wi]
    else:
      dp[i][wi] = max(dp[par][wi], dp[par][wi-w]+v)

def enum(node):
  res = []
  while node > 511:
    res.append(node)
    node //= 2
  return res, node

def calc(node, L):
  nodes, node = enum(node)
  n = len(nodes)
  res = 0
  total_v = total_w = 0
  for i in range(2**n):
    for j in range(n):
      if i>>j & 1:
        vj, wj = VW[nodes[j]]
        total_v += vj; total_w += wj
    if total_w <= L:
      res = max(res, dp[node, L-total_w]+total_v)
  return res

Q = int(input())
ans = []
for q in range(Q):
  node, L = map(int, input().split())
  if node <= 511:
    ans.append(dp[node][L])
  else:
    ans.append(calc(node, L))

print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
def main(): 
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  from bisect import bisect

  n = int(readline())
  g = []
  for i in range(n):
    v,W = map(int,readline().split())
    g.append((v,W))

  q = int(readline())
  for i in range(q):
    V,w = map(int,readline().split())
    c = []
    ans = 0
    while V > 0:
      c.append(g[V-1])
      V //= 2
    d = []
    e = []
    h = n//2-1
    H = n-h
    for i in range(2**h):
      cw = 0
      cv = 0
      for j,cj in enumerate(c[:h]):
        if (i>>j)&1 == 1:
          cw += cj[1]
          cv += cj[0]
      d.append((cv,cw))

    for i in range(2**H):
      cw = 0
      cv = 0
      for j,cj in enumerate(c[h:]):
        if (i>>j)&1 == 1:
          cw += cj[1]
          cv += cj[0]
      e.append((cv,cw))

    from operator import itemgetter
    e = sorted(e,key=itemgetter(1))

    Ev = [0]
    Ew = [0]
    ch = 0
    for i in range(1,len(e)):
      ev,ew = e[i]
      if ev > ch:
        Ev.append(ev)
        Ew.append(ew)
        ch = ev

    for i in d:
      Cv,Cw = i
      if Cw > w:
        continue
      ind = bisect(Ew,w-Cw)
      cc = Cv+Ev[ind-1]
      ans = max(cc,ans)

    print(ans)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**9)

def main():
    n = int(ipt())
    data = [(0,0)]
    for _ in range(n):
        v,w = map(int,ipt().split())
        data.append((v,w))
    q = int(ipt())
    dp = [[0]*(10**5+1) for _ in range(n+1)]
    dp[0][10**5] = -1

    for i in range(1,min(512,n+1)):
        dpp = dp[i//2]
        vi,wi = data[i]
        dpn = dp[i]
        dpn[:wi:] = dpp[:wi:]
        for j,dpj in enumerate(dpp[wi::]):
            dpjm = dpp[j]
            if dpj < dpjm+vi:
                dpn[j+wi] = dpjm+vi
            else:
                dpn[j+wi] = dpj

    def solve(i):
        dpn = dp[i]
        dpp = dp[i//2]
        if dpn[10**5] != 0:
            return dpn
        if dpp[10**5] == 0:
            solve(i//2)
        vi,wi = data[i]
        dpn[:wi:] = dpp[:wi:]
        for j,dpj in enumerate(dpp[wi::]):
            dpjm = dpp[j]
            if dpj < dpjm+vi:
                dpn[j+wi] = dpjm+vi
            else:
                dpn[j+wi] = dpj
        return dpn

    for _ in [0]*q:
        v,l = map(int,ipt().split())
        print(solve(v)[l])

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
VW = [list(map(int,input().split())) for _ in range(N)]
Q = int(input())
vL = [list(map(int,input().split())) for _ in range(Q)]
M = 0
import math
for q in range(Q):
  x = vL[q][1]
  if x>M:
    M = x

D = int(math.log2(N)) + 1
K = D//2
Ddp = [[0] * (M+1) for _ in range(2**K)]
for i in range(1,2**K):
  V,W = VW[i-1]
  for j in range(M+1):
    if W<=j:
      Ddp[i][j] = max(Ddp[i//2][j-W] + V, Ddp[i//2][j])
    else:
      Ddp[i][j] = Ddp[i//2][j]
      

for q in range(Q):
  v,L = vL[q]
  if v<=2**K - 1:
    print(Ddp[v][-1])
  else:
    ans = 0
    x = int(math.log2(v)) + 1
    for i in range(2**(x - K)):
      y = v
      z = [0,0]
      for j in range(x - K):
        if i>>j&1:
          vw = VW[y-1]
          z[0] += vw[0]
          z[1] += vw[1]

        y //= 2
      if z[1]>M:
        continue
      else:
        ans = max(ans, Ddp[y][L-z[1]] + z[0])
    
  print(ans)