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: Wrong Answer

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

input = sys.stdin.buffer.readline

#'''
N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]
'''
N = 2 ** 18
vws = [(1, i%10 + 1) for i in range(N)]
#'''
half = 10

n = min(2**half, N)
vws_arr = np.array(vws)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[:], i4[:], i4, i4[:], i4[:])", cache = True)
def func(vs, ws, L, dp_, bits):
    values = np.zeros_like(bits, np.int32)
    weights = np.zeros_like(bits, np.int32)
    for i in range(len(vs)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vs[i]
        weights[indices] += ws[i]

    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])


bits = np.arange(1 << (18 - half)).astype(np.int32)
'''
Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V], bits[:1 << len(Vs)]))
'''

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
readline = sys.stdin.readline

def mergeup(A, vw):
    v, w = vw
    res = []
    N = len(A)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
            continue
        if A[idx][1] <=  A[jdx][1] + w:
            res.append(A[idx])
            idx += 1
        else:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
    return res

def mergedown(A, vw):
    v, w = vw
    res = []
    N = len(A)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            res.append(A[idx])
            idx += 1
            continue
        if A[idx][1] <= A[jdx][1] - w:
            res.append(A[idx])
            idx += 1
        else:
            if A[jdx][1] - w < 0:
                jdx += 1
                continue
            res.append((A[jdx][0]+v, A[jdx][1]-w, A[jdx][2]))
            jdx += 1
    return res


def calc(A, B):
    res = []
    N = len(A)
    M = len(B)
    adx = 0
    bdx = 0
    for _ in range(N+M):
        if adx == N:
            res.append(B[bdx])
            bdx += 1
            continue
        if bdx == M:
            res.append(A[adx])
            adx += 1
            continue
        if A[adx][1] < B[bdx][1]:
            res.append(A[adx])
            adx += 1
        else:
            res.append(B[bdx])
            bdx += 1
    return res
  
limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<12)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


R = [None]*(N+1)
R[0] = [(0, 0)]
for i in range(1, BS):
    R[i] = mergeup(R[i//2], VW[i])
    
table = [[] for _ in range(1+N)]
for i in range(1, Q+1):
    v, l = VL[i]
    table[v].append((0, l, i))
for i in range(1, N+1):
    table[i].sort(key = itemgetter(1))
for i in range(N, BS-1, -1):
    table[i] = mergedown(table[i], VW[i])
    table[i//2] = calc(table[i], table[i//2])

ans = [0]*(Q+1)
for i in range(1, BS):
    if table[i]:
        res = [R[i][0]]
        for j in range(1, len(R[i])):
            if res[-1][0] < R[i][j][0]:
                res.append(R[i][j])
        
        for k in range(len(table[i])-1, -1, -1):
            v, rw, idx = table[i][k]
            while res[-1][1] > rw:
                res.pop()
            ans[idx] = max(ans[idx], v+res[-1][0])
print('\n'.join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
readline = sys.stdin.readline

def mergeup(A, vw):
    v, w = vw
    res = []
    N = len(A)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
            continue
        if A[idx][1] <=  A[jdx][1] + w:
            res.append(A[idx])
            idx += 1
        else:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
    return res

def mergedown(A, vw):
    v, w = vw
    res = []
    N = len(A)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            res.append(A[idx])
            idx += 1
            continue
        if A[idx][1] <= A[jdx][1] - w:
            res.append(A[idx])
            idx += 1
        else:
            if A[jdx][1] - w < 0:
                jdx += 1
                continue
            res.append((A[jdx][0]+v, A[jdx][1]-w, A[jdx][2]))
            jdx += 1
    return res


def calc(A, B):
    res = []
    N = len(A)
    M = len(B)
    adx = 0
    bdx = 0
    for _ in range(N+M):
        if adx == N:
            res.append(B[bdx])
            bdx += 1
            continue
        if bdx == M:
            res.append(A[adx])
            adx += 1
            continue
        if A[adx][1] < B[bdx][1]:
            res.append(A[adx])
            adx += 1
        else:
            res.append(B[bdx])
            bdx += 1
    return res
  
limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(2, N, 1<<12)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


R = [None]*(N+1)
R[0] = [(0, 0)]
for i in range(1, BS+1):
    R[i] = mergeup(R[i//2], VW[i])
    
table = [[] for _ in range(1+N)]
for i in range(1, Q+1):
    v, l = VL[i]
    table[v].append((0, l, i))
for i in range(1, N+1):
    table[i].sort(key = itemgetter(1))
for i in range(N, BS-1, -1):
    table[i] = mergedown(table[i], VW[i])
    table[i//2] = calc(table[i], table[i//2])

ans = [0]*(Q+1)
for i in range(1, BS+1):
    if table[i]:
        res = [R[i][0]]
        for j in range(1, len(R[i])):
            if res[-1][0] < R[i][j][0]:
                res.append(R[i][j])
        
        for k in range(len(table[i])-1, -1, -1):
            v, rw, idx = table[i][k]
            while res[-1][1] > rw:
                res.pop()
            ans[idx] = max(ans[idx], v+res[-1][0])
print('\n'.join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def mergeup(A, vw):
    v, w = vw
    res = []
    N = len(A)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
            continue
        if A[idx][1] <=  A[jdx][1] + w:
            res.append(A[idx])
            idx += 1
        else:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
    return res

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
            continue
        if Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw


def calc(Av, Aw, Ai, Bv, Bw, Bi):
    rv, rw, ri = [], [], []
    N = len(Av)
    M = len(Bv)
    adx = 0
    bdx = 0
    for _ in range(N+M):
        if adx == N:
            rv.append(Bv[bdx])
            rw.append(Bw[bdx])
            ri.append(Bi[bdx])
            bdx += 1
            continue
        if bdx == M:
            rv.append(Av[adx])
            rw.append(Aw[adx])
            ri.append(Ai[adx])
            adx += 1
            continue
        if Aw[adx] < Bw[bdx]:
            rv.append(Av[adx])
            rw.append(Aw[adx])
            ri.append(Ai[adx])
            adx += 1
        else:
            rv.append(Bv[bdx])
            rw.append(Bw[bdx])
            ri.append(Bi[bdx])
            bdx += 1
    return rv, rw, ri
  
  
limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<11)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


R = [None]*(N+1)
R[0] = [(0, 0)]
for i in range(1, BS+1):
    R[i] = mergeup(R[i//2], VW[i])
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    Kv1, Kw1 = [Kv[0]], [Kw[0]]
    for j in range(1, len(Kv)):
        if Kv1[-1] > Kv[j]:
            Kv1.append(Kv[j])
            Kw1.append(Kw[j])
    Kv1.reverse()
    Kw1.reverse()
    for j in range(len(R[v])):
        vj, wj = R[v][j]
        if wj > l:
            break
        while wj > Kw1[-1]:

            Kw1.pop()
            Kv1.pop()
        ans[i] = max(ans[i], vj+Kv1[-1])

print('\n'.join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
import sys
from time import time
readline = sys.stdin.readline

def mergeup(A, vw):
    v, w = vw
    res = []
    N = len(A)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
            continue
        if A[idx][1] <=  A[jdx][1] + w:
            res.append(A[idx])
            idx += 1
        else:
            if A[jdx][1] + w > limit:
                break
            res.append((A[jdx][0] + v, A[jdx][1] + w))
            jdx += 1
    return res

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
            continue
        if Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw


def calc(Av, Aw, Ai, Bv, Bw, Bi):
    rv, rw, ri = [], [], []
    N = len(Av)
    M = len(Bv)
    adx = 0
    bdx = 0
    for _ in range(N+M):
        if adx == N:
            rv.append(Bv[bdx])
            rw.append(Bw[bdx])
            ri.append(Bi[bdx])
            bdx += 1
            continue
        if bdx == M:
            rv.append(Av[adx])
            rw.append(Aw[adx])
            ri.append(Ai[adx])
            adx += 1
            continue
        if Aw[adx] < Bw[bdx]:
            rv.append(Av[adx])
            rw.append(Aw[adx])
            ri.append(Ai[adx])
            adx += 1
        else:
            rv.append(Bv[bdx])
            rw.append(Bw[bdx])
            ri.append(Bi[bdx])
            bdx += 1
    return rv, rw, ri
  
  
limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]

N = 1<<18
VW = [None] + [(1, 1) for _ in range(N)]
BS = min(N, 1<<11)

t1 = time()

Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]

Q = 100000
VL = [None] + [(1<<18, i+1) for i in range(Q)]

R = [None]*(N+1)
R[0] = [(0, 0)]
for i in range(1, BS+1):
    R[i] = mergeup(R[i//2], VW[i])

ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    Kv1, Kw1 = [Kv[0]], [Kw[0]]
    for j in range(1, len(Kv)):
        if Kv1[-1] > Kv[j]:
            Kv1.append(Kv[j])
            Kw1.append(Kw[j])
    Kv1.reverse()
    Kw1.reverse()
    for j in range(len(R[v])):
        vj, wj = R[v][j]
        if wj > l:
            break
        while wj > Kw1[-1]:

            Kw1.pop()
            Kv1.pop()
        ans[i] = max(ans[i], vj+Kv1[-1])

print('\n'.join(map(str, ans[1:])))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.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)]

K = N.bit_length() // 2
M = 10 ** 5 + 1

dp = [[0] * M for _ in range(2**K)]
for i in range(1, 2**K):
    for j in range(1, M):
        if j >= VW[i-1][1]:
            dp[i][j] = max(dp[i//2][j], dp[i//2][j-VW[i-1][1]] + VW[i-1][0])
        else:
            dp[i][j] = dp[i//2][j]

for v, L in vL:
    if v < 2**K:
        print(dp[v][L])
        continue

    k2 = v.bit_length() - K
    v2 = v >> k2

    ans = 0
    dv, dw = [0]*(2**k2), [0]*(2**k2)
    for i in range(1, 2**k2):
        msb = i.bit_length()
        dv[i] = dv[i - (1 << (msb - 1))] + VW[(v >> (msb - 1)) - 1][0]
        dw[i] = dw[i - (1 << (msb - 1))] + VW[(v >> (msb - 1)) - 1][1]

        if dw[i] <= L:
            ans = max(ans, dp[v2][L-dw[i]] + dv[i])

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
from numba import njit
input = sys.stdin.buffer.readline

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

n = min(2**1, N)

dp = np.zeros((n, 10**5+1), np.int64)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])

@njit(cache = True)
def func(vws_choose, L):
    bits = np.arange(1 << len(vws_choose))
    values = np.zeros_like(bits, np.int64)
    weights = np.zeros_like(bits, np.int64)
    for i in range(len(vws_choose)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vws_choose[i][0]
        weights[indices] += vws_choose[i][1]

    mask = (weights <= L)     
    print(np.amax(dp[V][L - weights[mask]] + values[mask]))


Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V][L])
    else:
        vws_choose = []
        while V >= n:
            vws_choose.append(vws[V])
            V = (V-1) // 2

        func(vws_choose, L)

Submission status: Wrong Answer

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    mx=10**5
    n=II()
    # 上半分をDP
    pn=min(511,n)
    vw=LLI(n)
    dp=[[0]*(mx+1) for _ in range(pn)]
    v,w=vw[0]
    dp[0][w:]=[v]*(mx+1-w)
    for nu in range(1,pn):
        v,w=vw[nu]
        u=(nu-1)//2
        for j in range(w,mx+1):
            dp[nu][j]=max(dp[u][j],dp[u][j-w]+v)
    #p2D(dp)

    q=II()
    for _ in range(q):
        u,m=MI()
        u-=1
        # 上半分のときはDPから
        if u<pn:print(dp[u][m])
        else:
            #下半分を全列挙
            ss=[(0,0)]
            while u>=pn:
                dv,dw=vw[u]
                for v,w in ss[:]:
                    if w+dw>m:continue
                    ss.append((v+dv,w+dw))
                u=(u-1)//2
                #print(u,ss)

            # 下半分を上半分のDPと組み合わせて最大値を求める
            ans=-1
            for v,w in ss:
                cur=v+dp[u][m-w]
                if cur>ans:ans=cur
            print(ans)

main()

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
vw = []
for i in range(n):
  vw.append(tuple(map(int,input().split())))
q = int(input())
vl = []
maxl = 0
for i in range(q):
  vl.append(tuple(map(int,input().split())))
  maxl = max(vl[i][1],maxl)

h = int(math.log(n,2))//2
pdp = [[0 for _ in range(maxl+1)] for _ in range(n+1)] 
for u in range(2**h,2**(h+1)):
  d = []
  uu = u
  while(uu > 0):
    d.append(vw[uu-1])
    uu //= 2
  dp = [[0 for _ in range(maxl+1)] for _ in range(len(d)+1)]
  for j in range(len(d)):
    for k in range(maxl+1):
      dp[j+1][k] = dp[j][k]
      if k-d[j][1] >= 0:
        dp[j+1][k] = max(dp[j][k],dp[j][k-d[j][1]]+d[j][0])
  #print(u,d,len(d),dp)
  pdp[u] = dp[len(d)][:]

for i in range(q):
  v,l = vl[i]
  d = []
  while(v >= 2**(h+1)):
    d.append(vw[v-1])
    v //= 2
  m = len(d)
  ans = 0
  for j in range(1<<m):
    sv,sl = 0,0
    for k in range(m):
      if (j>>k)&1 == 1:
        sv += d[k][0]
        sl += d[k][1]
    if sl > l:
      continue
    ans = max(sv+pdp[v][l-sl],ans)
  print(ans)

Submission status: Wrong Answer

Solution code:
import sys

int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    mx=10**5
    n=II()
    # 上半分をDP
    pn=min(511,n)
    vw=LLI(n)
    dp=[[0]*(mx+1) for _ in range(pn)]
    v,w=vw[0]
    dp[0][w:]=[v]*(mx+1-w)
    for nu in range(1,pn):
        v,w=vw[nu]
        u=(nu-1)//2
        for j in range(w,mx+1):
            dp[nu][j]=max(dp[u][j],dp[u][j-w]+v)
    #p2D(dp)

    q=II()
    for _ in range(q):
        u,m=MI()
        u-=1
        # 上半分のときはDPから
        if u<pn:print(dp[u][m])
        else:
            #下半分を全列挙
            ss=[(0,0)]
            while u>=pn:
                nss=[]
                i=j=0
                sn=len(ss)
                dv,dw=vw[u]
                while i<sn or j<sn:
                    v0=v1=w0=w1=10**9
                    if i<sn:v0,w0=ss[i]
                    if j<sn:v1,w1=ss[j]
                    v1,w1=v1+dv,w1+dw
                    if w0<w1:i+=1;v,w=v0,w0
                    else:j+=1;v,w=v1,w1
                    if w>m:break
                    if nss and nss[-1][1]==w:
                        if nss[-1][0]<v:nss.pop()
                        else:continue
                    if nss and nss[-1][0]>=v:continue
                    nss.append((v,w))
                ss=nss
                u=(u-1)//2
            #print(ss)

            # 下半分を上半分のDPと組み合わせて最大値を求める
            ans=-1
            for v,w in ss:
                cur=v+dp[u][m-w]
                if cur>ans:ans=cur
            print(ans)

main()

Submission status: Wrong Answer

Solution code:
import sys
import math
input = sys.stdin.buffer.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)]

K = math.ceil(math.log2(N)) // 2
M = 10 ** 5 + 1

dp = [[0] * M for _ in range(2**K)]
for i in range(1, 2**K):
    for j in range(1, M):
        if j >= VW[i-1][1]:
            dp[i][j] = max(dp[i//2][j], dp[i//2][j-VW[i-1][1]] + VW[i-1][0])

for v, L in vL:
    if v < 2**K:
        print(dp[v][L])
        continue

    k2 = 0
    v2 = v
    while v2 >= 2**K:
        k2 += 1
        v2 >>= 1

    ans = 0
    for i in range(2**k2):
        sv, sw = 0, 0
        for j in range(k2):
            if (i >> j) & 1:
                sv += VW[(v >> j) - 1][0]
                sw += VW[(v >> j) - 1][1]

        if sw <= L:
            ans = max(ans, dp[v2][L-sw] + sv)

    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vs=[]
    ws=[]
    costs=tuple(tuple(map(int, input().split())) for i in range(N))
    visited=[0]*N
    Q=int(input())
    qs= tuple(tuple(map(int, input().split())) for i in range(Q))
    maxL=int(max([qs[i][1] for i in range(Q)]))

    
    #マージソートを利用してlog(2**N)を消す
    for v,L in qs:
        if v==1:
            v,w=costs[0]
            if w<=L:print(v)
            else:print(0)
            continue

        n=[]
        while v:
            n.append(costs[v-1])
            v=v//2
        ln=len(n)
        n1=n[:ln//2]
        n2=n[ln//2:]
        
        n1c=[(0,0)]
        n2c=[(0,0)]

        #print(n2)
        for v,w in n1:
            
            ln1c=len(n1c)
            n1ca=[(n1cv+v,n1cw+w) for n1cv,n1cw in n1c]
            i1=0
            i2=0
            tot=[]
            #print(n1c,n1ca)
            while i1<ln1c and i2<ln1c:
                f1=0
                if n1c[i1][1]<n1ca[i2][1]:
                    f1=1  
                elif n1c[i1][1]==n1ca[i2][1] and n1c[i1][0]<=n1ca[i2][0]:
                    f1=1
                if f1:
                    tot.append(n1c[i1])
                    i1+=1
                else:
                    tot.append(n1ca[i2])
                    i2+=1
                
                    
            if i1<ln1c:
                tot+=n1c[i1:]
            else:
                tot+=n1ca[i2:]
            
            n1c=tot
            #print(n1c)
            
            

                
        for v,w in n2:
            f1=0
            ln2c=len(n2c)
            n2ca=[(n2cv+v,n2cw+w) for n2cv,n2cw in n2c]
            i1=0
            i2=0
            tot=[]
            while i1<ln2c and i2<ln2c:
                if n2c[i1][1]<n2ca[i2][1]:
                    f1=1  
                elif n2c[i1][1]==n2ca[i2][1] and n2c[i1][0]<=n2ca[i2][0]:
                    f1=1
                if f1:
                    tot.append(n2c[i1])
                    i1+=1
                else:
                    tot.append(n2ca[i2])
                    i2+=1

            if i1<ln2c:
                tot+=n2c[i1:]
            else:tot+=n2ca[i2:]
            
            n2c=tot
            #print(n2c,n2ca)
        #vmax=10**5+1
        #n1c.sort(key=lambda k: k[0]*vmax+k[1])
        #n2c.sort(key=lambda k: k[0]*vmax+k[1])
        
        

        j1=1
        for i in range(1,len(n1c)):
            if n1c[i][0]>n1c[j1-1][0]:
                n1c[j1]=n1c[i]
                j1+=1
        
        j2=1
        for i in range(1,len(n2c)):
            if n2c[i][0]>n2c[j2-1][0]:
                n2c[j2]=n2c[i]
                j2+=1

        j=j1-1
        ans=0
        for i in range(j2):
            v,w=n2c[i]
            while j>=0 and n1c[j][1]+w>L:
                j-=1
            if j==-1:
                break
            ans=max(ans,v+n1c[j][0])
        print(ans)
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    vs=[]
    ws=[]
    costs=tuple(tuple(map(int, input().split())) for i in range(N))
    visited=[0]*N
    Q=int(input())
    qs= tuple(tuple(map(int, input().split())) for i in range(Q))
    maxL=int(max([qs[i][1] for i in range(Q)]))

    
    #マージソートを利用してlog(2**N)を消す
    for v,L in qs:
        if v==1:
            v,w=costs[0]
            if w<=L:print(v)
            else:print(0)
            continue

        n=[]
        while v:
            n.append(costs[v-1])
            v=v//2
        ln=len(n)
        n1=n[:ln//2]
        n2=n[ln//2:]
        
        n1c=[(0,0)]
        n2c=[(0,0)]

        #print(n2)
        for v,w in n1:
            
            ln1c=len(n1c)
            n1ca=[(n1cv+v,n1cw+w) for n1cv,n1cw in n1c]
            i1=0
            i2=0
            tot=[]

            while i1<ln1c and i2<ln1c:
                f1=0
                if n1c[i1][1]<n1ca[i2][1]:
                    f1=1  
                elif n1c[i1][1]==n1ca[i2][1] and n1c[i1][0]<=n1ca[i2][0]:
                    f1=1
                if f1:
                    tot.append(n1c[i1])
                    i1+=1
                else:
                    tot.append(n1c[i2])
                    i2+=1
                    
            if i1<ln1c:
                tot+=n1c[i1:]
            else:tot+=n1ca[i2:]
            n1c=tot
            

                
        for v,w in n2:
            f1=0
            ln2c=len(n2c)
            n2ca=[(n2cv+v,n2cw+w) for n2cv,n2cw in n2c]
            i1=0
            i2=0
            tot=[]
            while i1<ln2c and i2<ln2c:
                if n2c[i1][1]<n2ca[i2][1]:
                    f1=1  
                elif n2c[i1][1]==n2ca[i2][1] and n2c[i1][0]<=n2ca[i2][0]:
                    f1=1
                if f1:
                    tot.append(n2c[i1])
                    i1+=1
                else:
                    tot.append(n2c[i2])
                    i2+=1

            if i1<ln2c:
                tot+=n2c[i1:]
            else:tot+=n2ca[i2:]
            
            n2c=tot
            #print(n2c,n2ca)
        #vmax=10**5+1
        #n1c.sort(key=lambda k: k[0]*vmax+k[1])
        #n2c.sort(key=lambda k: k[0]*vmax+k[1])
        
        j1=1
        for i in range(1,len(n1c)):
            if n1c[i][0]>n1c[j1-1][0]:
                n1c[j1]=n1c[i]
                j1+=1
        
        j2=1
        for i in range(1,len(n2c)):
            if n2c[i][0]>n2c[j2-1][0]:
                n2c[j2]=n2c[i]
                j2+=1

        j=j1-1
        ans=0
        for i in range(j2):
            v,w=n2c[i]
            while j>=0 and n1c[j][1]+w>L:
                j-=1
            if j==-1:
                break
            ans=max(ans,v+n1c[j][0])
        print(ans)
        #print(n1c,n2c)
if __name__ == "__main__":
    main()