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:
def examA():
    S = SI()
    ans = S[:3]
    print(ans)
    return

def examB():
    A, V = LI()
    B, W = LI()
    T = I()
    L = abs(A-B)
    v = V-W
    if v*T>=L:
        ans = "YES"
    else:
        ans = "NO"
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    for _ in range(min(60,K)):
        cur = N
        L = [0] * (N + 1)
        R = [0] * (N + 1)
        for i in range(N):
            a = A[i]
            if 0<i-a:
                L[i-a] += 1
            else:
                L[0] += 1
            if N>i+a+1:
                R[i+a+1] += 1
            else:
                R[N] += 1
            if cur>a:
                cur = a
        if cur==N:
            break
        A[0] = L[0]
        for i in range(1,N):
            A[i] = A[i-1]+L[i]-R[i]


    print(" ".join(map(str,A)))
    return

def examD():
    N = I()
    VW = [LI()for _ in range(N)]
    V = [-1]*N
    for i in range(1,N):
        a, b = (i-1)//2, i
        V[b] = a
    half = [[]for _ in range(512)]

    for i in range(min(N,512)):
        s = i
        candi = defaultdict(int)
        candi[0] = 0
        for _ in range(10):
            vc, wc = VW[s]
            ne = deepcopy(candi)

            for noww, nowv in candi.items():
                if ne[noww + wc] < nowv + vc:
                    ne[noww + wc] = nowv + vc
            candi = ne
            if s == 0:
                break
            s = V[s]
        half[i] = sorted(candi.items())

    Q = I()
    ans = [0]*Q
    #print(half)
    for q in range(Q):
        s, L = LI()
        s -= 1
        if s<512:
            cur = 0
            for noww, nowv in half[s]:
                if cur < nowv and noww <= L:
                    cur = nowv
            ans[q] = cur
            continue
        candi = defaultdict(int)
        candi[0] = 0
        for _ in range(10):
            vc, wc = VW[s]
            ne = deepcopy(candi)

            for noww, nowv in candi.items():
                if ne[noww + wc] < nowv + vc:
                    ne[noww + wc] = nowv + vc
            candi = ne
            s = V[s]
            if s<512:
                break
        #print(candi)
        cur = 0
        for noww, nowv in candi.items():
            if cur<nowv and noww<=L:
                plus = bisect.bisect_left(half[s],L-noww)
                x = nowv+half[s][min(len(half[s]),plus)]
                if cur<x:
                    cur = nowv+x
        ans[q] = cur

    for v in ans:
        print(v)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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 = data[:2*n:2]
W = data[1:2*n:2]
q = data[2*n]
v = data[2*n+1::2]
L = 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**10まで前計算
b_len = min(10, n.bit_length()-1)

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))

for i in range(1,2**b_len):
    bef[i].sort()
#
# print(bef)
# print(len(bef))
# print(b_len,2**b_len)

ans = []
for vi,Li in zip(v,L):
    aft = [(0,0)]
    x = vi
    while(x >= 2**b_len):
        xw,xv = W[x-1],V[x-1]
        aft2 = aft[::]
        for jw,jv in aft:
            aft2.append((xw+jw,xv+jv))
        x //= 2
        aft = aft2[::]

    aft.sort(reverse=True)

    max_ans = 0
    max_bef_v = 0
    i_bef = 0
    for aw,av in aft:
        lim_w = Li - aw
        if(lim_w > Li):
            continue

        while(i_bef < 2**b_len):
            if(bef[x][i_bef][0] > lim_w):
                break
            max_bef_v = max(max_bef_v,bef[x][i_bef][1])
            i_bef += 1
        max_ans = max(max_ans, av + max_bef_v)

    ans.append(max_ans)

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

Submission status: Runtime Error

Solution code:
from collections import deque, Counter, defaultdict
from itertools import chain, combinations
import json
# import numpy as np
import bisect
import sys
import math
import bisect
from functools import lru_cache
import itertools

sys.setrecursionlimit(10 ** 8)

M = 10 ** 9 + 7
INF = 10 ** 17


def main():
    # # N, K = [int(a) for a in input().split()]
    # # A = [int(a) for a in input().split()]
    # K=200000
    # # T = int(input())
    # # A = [int(a) for a in input().split()]
    # # T1, T2, T3 = [int(a) for a in input().split()]
    # A = [0]*100000
    #
    # for _ in range(K):
    #     AA = [1] * len(A)
    #     flag = True
    #     for i, ai in enumerate(A):
    #         if ai != len(A):
    #             flag = False
    #         for ii in range(ai):
    #             ii += 1
    #             if i + ii < len(A):
    #                 AA[i + ii] += 1
    #             if i - ii >= 0:
    #                 AA[i - ii] += 1
    #     A = AA
    #     if flag:
    #         return print(888888)
    #     print(A)
    # print(A)
    N = int(input())
    VW = [[int(a) for a in input().split()] for _ in range(N)]
    Q = int(input())
    uL = [[int(a) for a in input().split()] for _ in range(Q)]

    DP = [
        [0] * (100002)
        for _ in range(N)
    ]

    aaaaa = dict()
    for u, L in uL:
        aaaaa[u] = max(aaaaa.get(u, 0), L)
    aaa = sorted(aaaaa.items(), key=lambda k: k[0], reverse=True)
    for k, v in aaa:
        uu = k
        while True:
            uu = uu // 2
            if uu in aaaaa:
                if aaaaa[uu] <= v:
                    del aaaaa[uu]
            if uu == 0:
                break

    mem = [0] * N
    for u, L in aaaaa.items():
        parents_index = []
        uu = u
        while True:
            parents_index.append(uu - 1)
            uu = uu // 2
            if uu == 0:
                break
        parents_index.reverse()

        prev = None
        for i in parents_index:
            v, ww = VW[i]
            for w in range(mem[i], L + 1):
                if prev is None:
                    if w >= ww:
                        DP[i][w] = v
                    else:
                        DP[i][w] = 0
                else:
                    if w >= ww:
                        DP[i][w] = max(DP[prev][w - ww] + v, DP[prev][w])
                    else:
                        DP[i][w] = DP[prev][w]
            prev = i
            mem[i] = L + 1

    for u, L in uL:
        print(DP[u - 1][L])


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def examA():
    S = SI()
    ans = S[:3]
    print(ans)
    return

def examB():
    A, V = LI()
    B, W = LI()
    T = I()
    L = abs(A-B)
    v = V-W
    if v*T>=L:
        ans = "YES"
    else:
        ans = "NO"
    print(ans)
    return

def examC():
    N, K = LI()
    A = LI()
    for _ in range(min(60,K)):
        cur = N
        L = [0] * (N + 1)
        R = [0] * (N + 1)
        for i in range(N):
            a = A[i]
            if 0<i-a:
                L[i-a] += 1
            else:
                L[0] += 1
            if N>i+a+1:
                R[i+a+1] += 1
            else:
                R[N] += 1
            if cur>a:
                cur = a
        if cur==N:
            break
        A[0] = L[0]
        for i in range(1,N):
            A[i] = A[i-1]+L[i]-R[i]


    print(" ".join(map(str,A)))
    return

def examD():
    N = I()
    VW = [LI()for _ in range(N)]
    V = [-1]*N
    for i in range(1,N):
        a, b = (i-1)//2, i
        V[b] = a
    half = [[]for _ in range(512)]

    for i in range(min(N,512)):
        s = i
        candi = defaultdict(int)
        candi[0] = 0
        for _ in range(9):
            vc, wc = VW[s]
            ne = deepcopy(candi)

            for noww, nowv in candi.items():
                if ne[noww + wc] < nowv + vc:
                    ne[noww + wc] = nowv + vc
            candi = ne
            if s == 0:
                break
            s = V[s]
        half[i] = sorted(candi.items())

    Q = I()
    ans = [0]*Q
    #print(half)
    for q in range(Q):
        s, L = LI()
        s -= 1
        if s<512:
            cur = 0
            for noww, nowv in half[s]:
                if cur < nowv and noww <= L:
                    cur = nowv
            ans[q] = cur
            continue
        candi = defaultdict(int)
        candi[0] = 0
        for _ in range(9):
            vc, wc = VW[s]
            ne = deepcopy(candi)

            for noww, nowv in candi.items():
                if ne[noww + wc] < nowv + vc:
                    ne[noww + wc] = nowv + vc
            candi = ne
            s = V[s]
            if s<512:
                break
        #print(candi)
        cur = 0
        for noww, nowv in candi.items():
            if cur<nowv and noww<=L:
                plus = bisect.bisect_left(half[s],L-noww)
                cur = nowv+half[s][plus]
        ans[q] = cur


    for v in ans:
        print(v)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[2]:


import math
import numpy as np


# In[7]:


def knapsack(data,W):
    N = len(data)
    
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i]=0

    #DP
    for i in range(N):
        for w in range(W+1):
            if data[i][1]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-data[i][1]]+data[i][0], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]


# In[8]:


def func(vw, v,l):
    mylist = [vw[v//(2**x)-1] for x in range(int(math.log2(v)+1))]
    
    ans = knapsack(mylist,l)
    print(ans)


# In[3]:


N = int(input())
vw = []
for i in range(N):
    tmp = list(map(int, input().split()))
    vw.append(tmp)
Q = int(input())

for p in range(Q):
    v, l = map(int,input().split())
    func(vw, v, l)

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)]
    dpd = [-1]*(n+1)
    dpd[0] = 1

    def solve(i):
        if dpd[i//2] == -1:
            solve(i//2)
            dpd[i//2] = 1
        dpn = dp[i]
        dpp = dp[i//2]
        vi,wi = data[i]
        for j,dpj in enumerate(dpp):
            if j < wi:
                dpn[j] = dpj
            else:
                dpw = dpp[j-wi]
                if dpj < dpw+vi:
                    dpn[j] = dpw+vi
                else:
                    dpn[j] = dpj
        return

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

    return

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[2]:


import math
import numpy as np


# In[3]:


def main():
    N = int(input())
    vw = []
    for i in range(N):
        tmp = list(map(int, input().split()))
        vw.append(tmp)
    Q = int(input())
    
    for p in range(Q):
        v, l = map(int,input().split())
        func(vw, v, l)


# In[7]:


def knapsack(data,W):
    N = len(data)
    
    #初期化
    inf=float("inf")
    dp=[[-inf for i in range(W+1)] for j in range(N+1)]
    for i in range(W+1):
        dp[0][i]=0

    #DP
    for i in range(N):
        for w in range(W+1):
            if data[i][1]<=w: #dp[i][w-weight[i]の状態にi番目の荷物が入る可能性がある
                dp[i+1][w]=max(dp[i][w-data[i][1]]+data[i][0], dp[i][w])
            else: #入る可能性はない
                dp[i+1][w]=dp[i][w]
    return dp[N][W]


# In[8]:


def func(vw, v,l):
    mylist = [vw[v//(2**x)-1] for x in range(int(math.log2(v)+1))]
    
    ans = knapsack(mylist,l)
    print(ans)


# In[ ]:


if __name__ == "__main__":
    main()


# In[ ]:

Submission status: Runtime Error

Solution code:
def knapsack_meetinthemiddle(n, cap, item):
    if n % 2 != 0: item.append((0, 0))
    m = (n + 1) // 2
    M = 2**m
    item1 = item[:m]
    item2 = item[m:]
    S1 = [None] * (M)
    S2 = [None] * (M)
    for i in range(M):
        sumv1, sumw1, sumv2, sumw2 = 0, 0, 0, 0
        for j in range(m):
            if (i >> j) & 1:
                v1, w1 = item1[j]
                v2, w2 = item2[j]
                sumv1 += v1
                sumw1 += w1
                sumv2 += v2
                sumw2 += w2
        S1[i] = (sumw1, sumv1)
        S2[i] = (sumw2, sumv2)
    S1.sort()
    S2.sort()
    res, j, tmp = 0, 0, 0
    for sw1, sv1 in S1[::-1]:
        if sw1 > cap: continue
        while j < M and sw1 + S2[j][0] <= cap:
            tmp = max(tmp, S2[j][1])
            j += 1
        res = max(res, sv1 + tmp)
    return res

N = int(input())

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

Q = int(input())

if N < 2**9:
    for _ in range(Q):
        u, L = map(int, input().split())
        item = []
        cnt = 0
        while u:
            item.append(I[u - 1])
            cnt += 1
            u //= 2
        print(knapsack_meetinthemiddle(cnt, L, item))

else:
    T = [[None] * (2**9) for _ in range(2**8)]
    for i in range(2**8, 2**9):
        for j in range(2**9):
            sumv, sumw = 0, 0
            for k in range(9):
                if (j >> k) & 1:
                    v, w = I[((i + 1) << k) - 1]
                    sumv += v
                    sumw += w
            T[i][j] = (sumw, sumv)
        T[i].sort()

    for _ in range(Q):
        u, L = map(int, input().split())
        if u < 2**9:
            item = []
            cnt = 0
            while u:
                item.append(I[u - 1])
                cnt += 1
                u //= 2
            print(knapsack_meetinthemiddle(cnt, L, item))
        else:
            item = []
            cnt = 0
            while u >= 2**9:
                item.append(I[u - 1])
                cnt += 1
                u //= 2
            S = [None] * (2**cnt)
            for j in range(2**cnt):
                sumv, sumj = 0, 0
                for k in range(cnt):
                    if (j >> k) & 1:
                        v, w = item[k]
                        sumv += v
                        sumw += w
                S[j] = (sumw, sumv)
            S.sort()
            #T[u - 2**8]
            res, j, tmp = 0, 0, 0
            for sw, sv in S[::-1]:
                if sw > L: continue
                while j < 2**9 and sw + T[u - 2**8][0] <= L:
                    tmp = max(tmp, T[u - 2**8][1])
                    j += 1
                res = max(res, sv + tmp)
            print(res)

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N = int(input())
VW = int_mtx(N)
Q = int(input())
vL = int_mtx(Q)

for i in range(Q):
    v = vL[i,0]
    L = vL[i,1]
    Node = []
    while True:
        Node.append(v)
        if v == 1:
            break
        v = int(v/2)

    dp = np.zeros(L+1)
    for n in range(1,len(Node)+1):
        V = VW[Node[n-1]-1,0]
        W = VW[Node[n-1]-1,1]
        dp[W:] = np.maximum(dp[W:], dp[:L+1-W]+V )

    print(int(dp[L]))

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)]
    dpd = [-1]*(n+1)
    dpd[0] = 1

    def solve(i):
        if dpd[i//2] == -1:
            dp[i//2] = solve(i//2)
            dpd[i//2] = 1
        dpp = dp[i//2]
        dpn = [0]*(10**5+1)
        vi,wi = data[i]
        for j in range(10**5+1):
            dpj = dpp[j]
            if j < wi:
                dpn[j] = dpj
            else:
                dpw = dpp[j-wi]
                if dpj < dpw+vi:
                    dpn[j] = dpw+vi
                else:
                    dpn[j] = 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:
import sys
sys.setrecursionlimit(10**9)
import sys
input = sys.stdin.readline

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)]
import numpy as np
dp=np.full((n+1,10**5+1),-1,int)
dp[:,0]=0
dp[1,:vw[0][1]]=0
dp[1,vw[0][1]:]=vw[0][0]
def func(i,l):
  if dp[i,l]>-1:
    return dp[i,l]
  v,w=vw[i-1]
  ret=0
  ret=max(func(i//2,l),func(i//2,l-w)+v if l-w>=0 else 0)
  dp[i,w]=ret
  return ret
for v,l in vl:
  print(func(v,l))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit

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

A = 2

# ノード、重さ→価値
@njit('(i4,i4[:],i4[:])', cache=True)
def precompute(N, V, W):
    U = 10**5 + 10
    dp = np.zeros((A, U), np.int32)
    for v in range(1, min(A, N)):
        p = v // 2
        dp[v] = dp[p]
        dp[v, W[v]:] = np.maximum(dp[v, W[v]:], dp[p, :-W[v]] + V[v])
        for i in range(1, U):
            dp[v][i] = max(dp[v][i], dp[v][i - 1])
    return dp

@njit('(i4,i4[:],i4[:],i4[:],i4[:])', cache=True)
def main(N, V, W, v, L):
    dp = precompute(N, V, W)
    values = np.empty(1024, np.int32)
    weights = np.empty(1024, np.int32)

    def solve(i, lim, values, weights):
        if i < A:
            return dp[i][lim]
        values[0] = 0
        weights[0] = 0
        p = 0
        while i >= A:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j] + V[i]
                weights[j + (1 << p)] = weights[j] + W[i]
            p += 1
            i >>= 1
        best = 0
        for n in range(1 << p):
            if weights[n] > lim:
                continue
            x = dp[i][lim - weights[n]] + values[n]
            best = max(best, x)
        return best

    Q = len(v)
    for i in range(Q):
        x = solve(v[i], L[i], values, weights)
        print(x)

N = int(readline())
stdin = np.array(read().split(), np.int32)
V = np.zeros(N + 1, np.int32)
W = np.zeros(N + 1, np.int32)
V[1:] = stdin[:N + N:2]
W[1:] = stdin[1:N + N:2]
query = stdin[N + N + 1:]
v, L = query[::2], query[1::2]

main(N, V, W, v, L)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**10)
import sys
input = sys.stdin.readline

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)]
import numpy as np
dp=np.full((n+1,10**5+1),-1,int)
dp[:,0]=0
dp[1,:vw[0][1]]=0
dp[1,vw[0][1]:]=vw[0][0]
def func(i,l):
  if dp[i,l]>-1:
    return dp[i,l]
  v,w=vw[i-1]
  ret=0
  ret=max(func(i//2,l),func(i//2,l-w)+v if l-w>=0 else 0)
  dp[i,w]=ret
  return ret
for v,l in vl:
  print(func(v,l))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
import sys
input = sys.stdin.readline

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)]
import numpy as np
dp=np.full((n+1,10**5+1),-1,int)
dp[:,0]=0
dp[1,:vw[0][1]]=0
dp[1,vw[0][1]:]=vw[0][0]
def func(i,l):
  if dp[i,l]>-1:
    return dp[i,l]
  v,w=vw[i-1]
  ret=0
  ret=max(func(i//2,l),func(i//2,l-w)+v if l-w>=0 else 0)
  dp[i,w]=ret
  return ret
for v,l in vl:
  print(func(v,l))

Submission status: Runtime Error

Solution code:
n = int(input())

S = [list(map(int, input().split())) for _ in range(n)]
q = int(input())

vl = [list(map(int, input().split())) for _ in range(q)]

dp = [[0]*250 for _ in range(n+1)]


def knapsack(v, L):
    if v == 1:
        if S[v-1][1] > L:
            dp[v][L] = 0
            return 0
        else:
            dp[v][L] = S[v-1][0]
            return S[v-1][0]
    if dp[v][L] != 0:
        return dp[v][L]
    if L < S[v-1][1]:
        dp[v][L] = dp[v//2][L]
    else:
        #print(knapsack(v//2, L))
        #print(knapsack(v//2, L-S[v-1][1])+S[v-1][0])
        dp[v][L] = max(knapsack(v//2, L),
                       knapsack(v//2, L-S[v-1][1])+S[v-1][0])
    return dp[v][L]


for v, L in vl:
    print(knapsack(v, L))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

N = int(input())
VW = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
Q = int(input())
vL = [list(map(int,input().split())) for i in range(Q)]
vs,Ls = zip(*vL)

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = sorted(list(set(appear)))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = dpinit((M+1,maxL + 2),0)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        V,W = VW[ns]
        s = dic[s]
        ns = dic[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
    ans.append(dp[orgv][L])

for a in ans:
    print(a)

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)]
    dpd = [-1]*(n+1)
    dpd[0] = 1

    def solve(i):
        if dpd[i] == 1:
            return dp[i]
        if dpd[i//2] == -1:
            solve(i//2)
            dpd[i//2] = 1
        dpp = dp[i//2]
        dpn = [0]*(10**5+1)
        vi,wi = data[i]
        for j in range(10**5+1):
            if j < wi:
                dpn[j] = dpp[j]
            else:
                if dpp[j] < dpp[j-wi]+vi:
                    dpn[j] = dpp[j-wi]+vi
                else:
                    dpn[j] = dpp[j]
        dp[i] = dpn
        dpd[i] = 1
        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:
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)]
    dpd = [-1]*(n+1)
    dpd[0] = 1

    def solve(i):
        if dpd[i] == 1:
            return dp[i]
        if dpd[i//2] == -1:
            solve(i//2)
            dpd[i//2] = 1
        dpp = dp[i//2]
        dpn = [0]*(10**5+1)
        vi,wi = data[i]
        for j in range(10**5+1):
            if j < wi:
                dpn[j] = dpp[j]
            else:
                if dpp[j] < dpp[j-wi]+vi:
                    dpn[j] = dpp[j-wi]+vi
                else:
                    dpn[j] = dpp[j]
        dp[i] = dpn
        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())
V=[0]
W=[0]
for _ in range(N):
    tmp1,tmp2=map(int,input().split())
    V.append(tmp1)
    W.append(tmp2)
    
Q=int(input())
v=[]
L=[]
for _ in range(N):
    tmp1,tmp2=map(int,input().split())
    v.append(tmp1)
    L.append(tmp2)
#v_は今いる場所
def explorer(V_,W_,v_,L_):
    if v_==1:
        if W_+W[1]<=L_ and V[1]>0:
            return V_+V[1]
        else:
            return V_
    elif W_+W[v_]<=L_ and V[1]>0:
        return max(explorer(V_+V[v_],W_+W[v_],v_//2,L_),explorer(V_,W_,v_//2,L_))
    else:
        return explorer(V_,W_,v_//2,L_)


for i in range(len(L)):
    print(explorer(0,0,v[i],L[i]))

Submission status: Runtime Error

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-

import numpy as np

def int_mtx(N):
    x = []
    for _ in range(N):
        x.append(list(map(int,input().split())))
    return np.array(x)

N = int(input())
VW = int_mtx(N)
Q = int(input())
vL = int_mtx(Q)

for i in range(Q):
    v = vL[i,0]
    L = vL[i,1]
    Node = []
    while True:
        Node.append(v)
        if v == 1:
            break
        v = int(v/2)

    N = len(Node)
    
    dp = np.array([ [0]*(L+1) ] * (N+1))
    for n in range(1,N+1):
        V = VW[Node[n-1]-1,0]
        W = VW[Node[n-1]-1,1]
        dp[n][:] = dp[n-1][:]
        dp[n][W:L+1] = np.maximum(dp[n-1][W:L+1], dp[n-1][:L+1-W]+V )

    print(dp[len(Node)][L])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    N = int(input())

    MAX_W = 10 ** 5 + 1

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

    for i in range(1, N + 1):
        V, W = map(int, input().split())
        for j in range(MAX_W):
            # print (i, j)
            if (j < W):
                dp[i][j] = dp[i // 2][j]
            else:
                dp[i][j] = max(dp[i // 2][j], dp[i // 2][j - W] + V)

    Q = int(input())
    for _ in range(Q):
        v, L = map(int, input().split())
        print (dp[v][L])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N=int(input())
V=[0]
W=[0]
for _ in range(N):
    tmp1,tmp2=map(int,input().split())
    V.append(tmp1)
    W.append(tmp2)
    
Q=int(input())
v=[]
L=[]
for _ in range(N):
    tmp1,tmp2=map(int,input().split())
    v.append(tmp1)
    L.append(tmp2)
#v_は今いる場所
def explorer(V_,W_,v_,L_):
    if v_==1:
        if W_+W[1]<=L_:
            return V_+V[1]
        else:
            return V_
    elif W_+W[v_]<=L_:
        return max(explorer(V_+V[v_],W_+W[v_],v_//2,L_),explorer(V_,W_,v_//2,L_))
    else:
        return explorer(V_,W_,v_//2,L_)

for i in range(len(L)):
    print(explorer(0,0,v[i],L[i]))