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 calc_rec(node):
    do_list=[node]
    while True:
        node//=2
        if node in D.keys():
            break
        else:
            do_list.append(node)
    for node in reversed(do_list):
        new_dp =calc_dp_step(D[node//2],node)
    return new_dp


def calc_dp_step(cur_dp,node_id):
    (node_val,node_weight) = nodes[node_id]
    new_dp=[Vmax]*Vmax
    for j in range(Vmax):
        if j<node_val: 
            new_dp[j] = cur_dp[j]
        else:
            new_dp[j] = min(cur_dp[j],cur_dp[j-node_val]+node_weight)
    D[node_id]=new_dp
    return new_dp

N = int(input())

nodes=[None]
for _ in range(N):
    v,w = map(int,input().split())
    nodes.append((v,w))

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

query_sort = sorted(query,key=lambda x:x[0])

D=dict()
Vmax=(10**5)*20

D[0]=[Wmax]*Vmax
D[0][0]=0
Q_ans=dict()
for v,L in query_sort:
    if v//2 in D.keys():
        cur_dp = D[v//2]
        new_dp = calc_dp_step(cur_dp,v)
    else:
        new_dp = calc_rec(v)
    for j in reversed(range(Vmax)):
        if new_dp[j]<=L:
            Q_ans[v]=j
            break

for v,_ in query:
    print(Q_ans[v])

Submission status: Runtime Error

Solution code:
#

import sys
input=sys.stdin.readline

def main():
    N=int(input())
    vw=[tuple(map(int,input().split())) for i in range(N)]
    vw=[(0,0)]+vw
    W=10**5
    dp=[[0]*(W+1) for i in range(N+1)]
    for i in range(1,W+1):
        if i < vw[1][1]:
            dp[1][i]=0
        else:
            dp[1][i]=vw[1][0]
    for i in range(2,N+1,2):
        for w in range(W+1):
            p=int(i//2)
            dp[i][w]=dp[p][w]
            dp[i+1][w]=dp[p][w]
            if w>=vw[i][1]:
                dp[i][w]=max(dp[i][w], dp[p][w-vw[i][1]]+vw[i][0])
            if w>=vw[i+1][1]:
                dp[i+1][w]=max(dp[i+1][w], dp[p][w-vw[i+1][1]]+vw[i+1][0])
    Q=int(input())
    for i in range(Q):
        v,L=map(int,input().split())
        print(dp[v][L])    
    
if __name__=="__main__":
    main()

Submission status: Runtime Error

Solution code:
INF = 10 ** 12
L = 10 ** 5 + 1
n=int(input())
vw=[]

def rec(x, uplimit_w):
  ans = 0
  if x == N:
    return 0

  # n番目の品物を使えない場合
  elif vws[x][1] > uplimit_w:
    return rec(x + 1, uplimit_w)

  # n番目の品物が使える時
  # -> n番目の品物は使った方がいいのか、使わない方がいいのか...?
  else:
    ans = max(
      rec(x + 1, uplimit_w),
      rec(x + 1, uplimit_w - vws[x][1]) + vws[x][0]
    )
    return ans

def solve():
  print(rec(0, l))

def main():
  solve()

for i in range(n):
  vw.append(list(map(int,input().split())))

q=int(input())

for i in range(q):
  v,l=map(int,input().split())
  vws=[vw[v-1]]
  while v>1:
    v=v//2
    vws.append(vw[v-1])
    N=len(vws)
  if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np
n=int(input())
V=[]
W=[]
for i in range(n):
  v,w=map(int,input().split())
  V.append(v)
  W.append(w)
V=np.array(V)
W=np.array(W)
q=int(input())
for _ in range(q):
  v,l=map(int,input().split())
  s=v
  p=[]
  z=0
  while s>=1:
    p.append[s]
    z+=1
    s=s//2
  weights＝W[p]
  values=V[p]


  dp={0:0}
  for i in range(z):
    w=weights[i]
    val=values[i]
    dplist=list(dp.keys())
    for c in dplist:
      p=c+w
      v=dp[c]+val
      if  p in dp and dp[p]>v:
        continue
      elif p<=l:
        dp[p]=v

  x=max(dp.values())
  print(x)

Submission status: Runtime Error

Solution code:
import sys
from heapq import heappop, heappush

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n = ni()
    bag = [tuple(nm()) for _ in range(n)]
    q = ni()
    query = [tuple(nm()) for _ in range(q)]
    ansd = dict()
    g = [None]* 2 ** 10

    def calc(v):
        W = 10**5 + 1
        res = [0] * w
        l = list()
        while v:
            l.append(bag[v-1])
            v >>= 1
        m = len(l)
        for bit in range(1 << m):
            cv = cw = 0
            for i in range(m):
                if bit & (1 << i):
                    cv += l[i][0]
                    cw += l[i][1]
                    if cw > W:
                        break
            else:
                if res[cw] < cv:
                    res[cw] = cv
        for i in range(m-1):
            if res[i+1] < res[i]:
                res[i+1] < res[i]
        return res


    for _v, L in query:
        v = _v
        if v < 2 ** 9:
            l = list()
            while v:
                l.append(bag[v-1])
                v >>= 1
            m = len(l)
            ans = 0
            for bit in range(1 << m):
                cv = cw = 0
                for i in range(m):
                    if bit & (1 << i):
                        cv += l[i][0]
                        cw += l[i][1]
                        if cw > L:
                            break
                else:
                    if cv > ans:
                        ans = cv

            ansd[(_v, L)] = ans

        else:
            l = list()
            while v >= 2 ** 9:
                l.append(bag[v-1])
                v >>= 1
            if g[v] is None:
                g[v] = calc(v)
            m = len(l)
            ans = 0
            for bit in range(1 << m):
                cv = cw = 0
                for i in range(m):
                    if bit & (1 << i):
                        cv += l[i][0]
                        cw += l[i][1]
                        if cw > L:
                            break
                else:
                    if cv + g[v][L-cw] > ans:
                        ans = cv + g[v][L-cw]
            ansd[(_v, L)] = ans

    for c in query:
        print(ansd[c])
    return

solve()

Submission status: Runtime Error

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

def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    dic = {}
    q = int(input())
    Q = []
    lm = 0
    for i in range(q):
        a,b = map(int,input().split())
        lm = max(b,lm)
        Q.append((a,b))
    d = np.zeros(lm+1,dtype=np.int64)
    if l[0][1] <= lm:
        d[l[0][1]] = l[0][0]
    dic[1] = d
    
    def dfs(x):
        if x in dic:
            return dic[x]
        
        v,w = l[x-1]
        li = copy.deepcopy(dfs(x//2))
        
        np.maximum(li[w:],li[:-w]+v,out=li[w:])
        dic[x] = li
        return li

    for a,b in Q:
        s = dfs(a)
        print(np.max(s[:b+1]))
if __name__ == "__main__":
    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 = 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**9まで前計算
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):
    if(vi==1):
        if(W[0] <= Li):
            ans.append(V[0])
        else:
            ans.append(0)
        continue

    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 < 0):
            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:
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)]
for vLi in vL:
    vi = vLi[0]
    Li = vLi[1] 
    vw = VW[vi-1]
    V = [0 for _ in range(Li+1)]
    while vi != 1:
        vw = VW[vi-1]
        Vi = vw[0]
        Wi = vw[1]
        for l in range(1,Li+1)[::-1]:
            if l >= Wi:
                V[l] = max(V[l],V[l-Wi] + Vi)
        vi = vi//2
    vw = VW[1]
    Vi = vw[0]
    Wi = vw[1]
    if Li >= Wi:
        print(max(V[Li],V[Li-Wi] + Vi))
    else:
        print(V[Li])

Submission status: Runtime Error

Solution code:
n=int(input())
V=[]
W=[]
for i in range(n):
  v,w=map(int,input().split())
  V.append(v)
  W.append(w)
q=int(input())
for _ in range(q):
  v,l=map(int,input().split())
  s=v
  p=[]
  z=0
  while s>=1:
    p.append[s]
    z+=1
    s=s//2
  weights＝W[p]
  values=V[p]


  dp={0:0}
  for i in range(z):
    w=weights.pop()
    val=values.pop()
    dplist=list(dp.keys())
    for c in dplist:
      p=c+w
      v=dp[c]+val
      if  p in dp and dp[p]>v:
        continue
      elif p<=l:
        dp[p]=v

  x=max(dp.values())
  print(x)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
import numpy as np


def f(li, w_max):
    d = defaultdict(int)
    for i in range(1 << len(li)):
        v_sm = 0
        w_sm = 0
        now = i
        cnt = 0
        while now:
            if now & 1:
                j = li[cnt]
                v, w = V[j-1], W[j-1]
                v_sm += v
                w_sm += w

            now >>= 1
            cnt += 1

        if w_sm <= w_max:
            d[w_sm] = max(d[w_sm], v_sm)

    return d


n = int(readline())
Z = np.array(read().split(), np.int64)
V = Z[0:2*n:2]
W = Z[1:2*n:2]
Q = Z[2*n]
U = Z[2*n+1::2]
L = Z[2*n+2::2]

for u, l in zip(U, L):
    li = []
    now = u
    while now:
        li.append(now)
        now //= 2

    ln = len(li)
    d1 = f(li[:ln//2], l)
    d2 = f(li[ln//2:], l)
    raise Exception

    W2 = np.array(list(d2.keys()), np.int64)
    V2 = np.array(list(d2.values()), np.int64)
    idx = np.argsort(W2)
    W2 = W2[idx]
    V2 = V2[idx]
    V2 = np.maximum.accumulate(V2)

    K1 = np.array(list(d1.keys()), np.int64)
    V1 = np.array(list(d1.values()), np.int64)
    IDX = np.searchsorted(W2, l - K1, "right") - 1
    VAL = V1 + V2[IDX]
    ans = VAL.max()
    print(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():
    def f(l, v, w):
        tmp = []
        for vi, wi in l:
            tmp.append((vi, wi))
            tmp.append((vi + v, wi + w))
        tmp.sort(key=lambda x: x[1])
        res = []
        pre = -1
        for value, key in tmp:
            if value > pre:
                res.append((value, key))
                pre = value
        return res
    n = II()
    vw = LIR(n)
    dp = [[(0,0)] for i in range(1 << n.bit_length() + 1)]
    dp[1] = [(0, 0), (vw[0][0], vw[0][1])]
    for i in range(1, (1 << n.bit_length() - 1)):
        dp[2 * i] = f(dp[i], vw[2 * i - 1][0], vw[2 * i - 1][1])
        dp[2 * i + 1] = f(dp[i], vw[2 * i][0], vw[2 * i][1])
    for _ in range(II()):
        v, L = LI()
        t = dp[v]
        ok = -1
        ng = len(t)
        while ng - ok > 1:
            mid = (ok + ng) // 2
            if t[mid][1] <= L:
                ok = mid
            else:
                ng = mid
        print(t[ok][0])

    return


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

Submission status: Runtime Error

Solution code:

n=int(input())
L=10**5
item=[(0,0)]
for i in range(n):
    v,w=map(int,input().split())
    item.append((v,w))

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

for k in range(item[1][1],L+1):
    dp[1][k]=item[1][0]
    
for i in range(2,n+1,2):
    for l in range(L+1):
        bi=i//2
        if item[i][1]<=l:
            dp[i][l]=max(dp[bi][l-item[i][1]]+item[i][0],dp[bi][l])
        else:
            dp[i][l]=dp[bi][l]
        try:
            if item[i+1][1]<=l:
                dp[i+1][l]=max(dp[bi][l-item[i+1][1]]+item[i+1][0],dp[bi][l])
            else:
                dp[i+1][l]=dp[bi][l]
        
Q=int(input())
for q in range(Q):
    u,l=map(int,input().split())
    print(dp[u][l])

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(1024)]

    for i in range(min(N,1024)):
        s = i
        candi = defaultdict(int)
        candi[0] = 0
        for _ in range(12):
            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<1024:
            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<1024:
                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])-1,plus)][1]
                if cur<x:
                    cur = nowv+x

        ans[q] = cur


    for v in ans:
        print(v)
    return

def examE():
    N, K, S, T = LI()

    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,bisect
input = sys.stdin.buffer.readline

n = int(input())

dg = 10**10 + 5

v = [0]*(n+1)
w = [0]*(n+1)
for i in range(1,n+1):
    v[i],w[i] = map(int,input().split())

a = [[] for i in range(2**9)]

for i in range(1,min(n+1,2**9)):
    if i == 1:
        a[i].append((w[1],v[1]))
    else:
        p = i//2
        tank = set([(w[i],v[i])])
        for ww,vv in a[p]:
            tank.add((ww,vv))
            if ww + w[i] <= 10**5:
                tank.add((ww+w[i],vv+v[i]))
        tank = list(tank)
        tank.sort()
        ma = -1
        for j in range(len(tank)):
            ww,vv = tank[j]
            if vv > ma:
                if j == len(tank)-1 or tank[j+1][0] != ww:
                    ma = vv
                    a[i].append(ww*dg + v)


Q = int(input())
for _ in range(Q):
    now,L = map(int,input().split())
    if now < 2**9:
        L = L*dg
        if a[now][0] > L:
            print(0)
        else:
            ok = 0
            ng = len(a[now])

            while ng - ok > 1:
                mid = (ok+ng)//2
                if a[now][mid] > L:
                    ng = mid
                else:
                    ok = mid
            print(a[now][ok]%dg)
    else:
        pp = [(0,0)]
        while now >= 2**9:
            tank = []
            for ww,vv in pp:
                if ww+w[now] <= L:
                    tank.append((ww+w[now],vv+v[now]))
            for e in tank:
                pp.append(e)
            now = now//2
        
        res = 0

        for ww,vv in pp:
            L -= ww

            L *= dg
            if a[now][0] > L:
                res = max(res,vv)
            else:
                ok = 0
                ng = len(a[now])

                while ng - ok > 1:
                    mid = (ok+ng)//2
                    if a[now][mid] > L:
                        ng = mid
                    else:
                        ok = mid
                res = max(res,a[now][ok]%dg + vv)
            L //= dg
            L += ww
        print(res)

Submission status: Runtime Error

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

top = set()
mid = set()

for v,l in vl:
    if v < 1<<9:
        top.add(v)
    elif v < 1<<10:
        mid.add(v)
    else:
        while 1<<10 <= v:
            v //= 2
        mid.add(v)

def get_parents(node,end=0):
    a = []
    while node > end:
        a.append(vw[node-1])
        node //= 2
    return a

from itertools import combinations
max_l = 10**5
def knapsack(vw_list, l, l_list=[0]*(max_l+1),):
    x = len(vw_list)
    ret = 0
    for i in range(x):
        for li in combinations(range(x), i+1):
            v_sum = 0
            w_sum = 0
            for j in li:
                v_sum += vw_list[j][0]
                w_sum += vw_list[j][1]
                if w_sum > l:
                    break
            if w_sum > l:
                continue
            res = l-w_sum
            ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(vw_list):
    x = len(vw_list)
    ret = [0]*(max_l+1)
    for i in range(x):
        for li in combinations(range(x), i+1):
            v_sum = 0
            w_sum = 0
            for j in li:
                v_sum += vw_list[j][0]
                w_sum += vw_list[j][1]
                if w_sum > l:
                    break
            if w_sum > max_l:
                continue
            ret[w_sum] = max(ret[w_sum], v_sum)
    return ret

d = dict()
for v in mid:
    a = get_parents(v)
    b = knapsack_mid(a)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = i
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        a = get_parents(v)
        ans[i] = knapsack(a,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<10 <= vv:
            vv //=2
        a = get_parents(v, end=vv)
        ans[i] = knapsack(a, l, l_list=d[vv])

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

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

import numpy as np
N = int(input())
VW = [list(mapint()) for _ in range(N)]
Q = int(input())
VL = [list(mapint()) for _ in range(Q)]
vset = set([v for v, l in VL])

memo = {}
def dfs(i, dp):
    v, w = VW[i-1]
    dp[w:] = np.maximum(dp[w:], dp[:-w]+v)
    if i in vset:
        memo[i] = list(dp)
    if i*2>N:
        return
    for j in range(2):
        dfs(i*2+j, np.copy(dp))

dfs(1, np.array([0]*(10**5+1)))
for q in range(Q):
    v, l = VL[q]
    print(memo[v][l])

Submission status: Runtime Error

Solution code:
n=int(input())
L=10**5
item=[(0,0)]
for i in range(n):
    v,w=map(int,input().split())
    item.append((v,w))

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

for k in range(item[1][1],L+1):
    dp[1][k]=item[1][0]
    
for i in range(2,n+1,2):
    for l in range(L+1):
        bi=i//2
        if item[i][1]<=l:
            dp[i][l]=max(dp[bi][l-item[i][1]]+item[i][0],dp[bi][l])
        else:
            dp[i][l]=dp[bi][l]

        if item[i+1][1]<=l:
            dp[i+1][l]=max(dp[bi][l-item[i+1][1]]+item[i+1][0],dp[bi][l])
        else:
            dp[i+1][l]=dp[bi][l]
        

Q=int(input())
for q in range(Q):
    u,l=map(int,input().split())
    print(dp[u][l])

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(2048)]

    for i in range(min(N,2048)):
        s = i
        candi = defaultdict(int)
        candi[0] = 0
        for _ in range(12):
            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<2048:
            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<2048:
                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])-1,plus)]
                #x = nowv + half[s][0]
                if cur<x:
                    cur = nowv+x
                """
        ans[q] = cur


    for v in ans:
        print(v)
    return

def examE():
    N, K, S, T = LI()

    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
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

ans = [0]*q

top = set()
mid = set()

for v,l in vl:
    if v < 1<<9:
        top.add(v)
    elif v < 1<<10:
        mid.add(v)
    else:
        while 1<<10 <= v:
            v //= 2
        mid.add(v)

def get_parents(node,end=0):
    a = []
    while node > end:
        a.append(vw[node-1])
        node //= 2
    return a

from itertools import combinations
max_l = 10**5
def knapsack(vw_list, l, l_list=[0]*(max_l+1),):
    x = len(vw_list)
    ret = 0
    for i in range(x):
        for li in combinations(range(x), i+1):
            v_sum = 0
            w_sum = 0
            for j in li:
                v_sum += vw_list[j][0]
                w_sum += vw_list[j][1]
                if w_sum > l:
                    break
            if w_sum > l:
                continue
            res = l-w_sum
            ret = max(ret, v_sum + l_list[res])
    return ret

def knapsack_mid(vw_list):
    x = len(vw_list)
    ret = [0]*(max_l+1)
    for i in range(x):
        for li in combinations(range(x), i+1):
            v_sum = 0
            w_sum = 0
            for j in li:
                v_sum += vw_list[j][0]
                w_sum += vw_list[j][1]
                if w_sum > l:
                    break
            if w_sum > max_l:
                continue
            ret[w_sum] = max(res[w_sum], v_sum)
    return ret

d = dict()
for v in mid:
    a = get_parents(v)
    b = knapsack_mid(a)
    for i in range(max_l):
        if b[i] > b[i+1]:
            b[i+1] = i
    d[v] = b

for i, (v,l) in enumerate(vl):
    if v in top:
        a = get_parents(v)
        ans[i] = knapsack(a,l)
    elif v in mid:
        ans[i] = d[v][l]
    else:
        vv = v
        while 1<<10 <= vv:
            vv //=2
        a = get_parents(v, end=vv)
        ans[i] = knapsack(a, l, l_list=d[vv])

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