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

Solution (Python):
import sys,random,time,bisect
input=sys.stdin.buffer.readline

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

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    while temp and temp[-1][1]>10**5:
        temp.pop()
    m=len(temp)
    for i in range(1,m):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(m-1):
        L=temp[i][1]
        R=temp[i+1][1]
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        for j in range(L,10**5+1):
            dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])

Solution (Python):
import sys,random,time,bisect
input=sys.stdin.buffer.readline

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

dp=[[] for i in range(2**9)]
def make_dp(v):
    t=[[0,0] for i in range(15)]
    V=v
    id=0
    while v>=1:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    temp=[[0,0] for i in range(2**n)]
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]
    temp.sort(key=lambda x:x[1])
    for i in range(1,2**n):
        temp[i][0]=max(temp[i][0],temp[i-1][0])

    dp[V]=[0]*(10**5+1)
    for i in range(2**n-1):
        L=temp[i][1]
        R=temp[i+1][1]
        if L>10**5:
            break
        elif R>10**5:
            R=10**5+1
        for j in range(L,R):
            dp[V][j]=temp[i][0]
    else:
        L=temp[-1][1]
        if L<=10**5:
            for j in range(L,10**5+1):
                dp[V][j]=temp[-1][0]

MAX=min(2**9,N+1)
for i in range(1,MAX):
    make_dp(i)

Q=int(input())
query=[[] for i in range(N+1)]
for i in range(Q):
    v,L=map(int,input().split())
    query[v].append((L,i))

ans=[0]*Q
temp=[[0,0] for i in range(2**9)]
t=[[0,0] for i in range(15)]
def solve(v):
    V=v
    id=0
    while v>=2**9:
        t[id]=vw[v]
        id+=1
        v//=2
    n=id
    for i in range(n):
        for j in range(2**i,2**(i+1)):
            temp[j][0]=temp[j-2**i][0]+t[i][0]
            temp[j][1]=temp[j-2**i][1]+t[i][1]

    for L,ID in query[V]:
        res=0
        for i in range(2**n):
            if L>=temp[i][1]:
                res=max(res,temp[i][0]+dp[v][L-temp[i][1]])
        ans[ID]=res

for i in range(1,N+1):
    if query[i]:
        solve(i)

for i in range(Q):
    print(ans[i])

Solution (Python):


from sys import stdin
import bisect

readline = stdin.readline
bisect_right = bisect.bisect_right

n = int(readline())

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

max_l = 10 ** 5
vshift = 21
mask = (1 << vshift) - 1


dp = [None] * min(n, 2 ** 12)


dp[0] = [(0 << vshift) + 0, (w[0] << vshift) + v[0]]

for u in range(1, len(dp)):
    parent = (u - 1) // 2

    ls = dp[parent][:]
    ls.extend(x + (w[u] << vshift) + v[u] for x in dp[parent]
              if (x >> vshift) + w[u] <= max_l)
    ls.sort()

    
    tail = 0
    for i in range(1, len(ls)):
        if (ls[tail] >> vshift) == (ls[i] >> vshift):
            ls[tail] = ls[i]
        elif (ls[tail] & mask) < (ls[i] & mask):
            tail += 1
            ls[tail] = ls[i]
    del ls[tail + 1:]
    dp[u] = ls

def solve(u, l):
    if u < len(dp):
        x = bisect_right(dp[u], (l << vshift) + mask) - 1
        return dp[u][x] & mask

    parent = (u - 1) // 2
    s = solve(parent, l)
    if l >= w[u]:
        s = max(s, v[u] + solve(parent, l - w[u]))
    return s

q = int(readline())
for i in range(q):
    u, l = map(int, readline().split())
    print(solve(u - 1, l))

Solution (Python):
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**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(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[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

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(vs, ws, L, dp[V]))

Solution (Python):
import sys
readline = sys.stdin.readline
def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            if Aw[jdx] + w > limit:
                break
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1

    return rv, rw

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


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


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
            Rv[i].append(vm)
            Rw[i].append(wm)
    
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
    cnt = len(Rv[v])-1
    ctr = 0
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ctr = max(ctr, kv+Rv[v][cnt])
    ans[i] = ctr

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

Solution (Python):
import sys
readline = sys.stdin.readline
def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            if Aw[jdx] + w > limit:
                break
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1

    return rv, rw

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


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


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
            Rv[i].append(vm)
            Rw[i].append(wm)
    
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
    cnt = len(Rv[v])-1
    ctr = 0
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ctr = max(ctr, kv+Rv[v][cnt])
    ans[i] = ctr

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

Solution (Python):
n =int(input())
vw = [(0,0)]  
for _ in range(n):
    vw.append(list(map(int,input().split())))

A  =10
N = min(1<<A,n+1)
memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q = int(input())
ans_ = [0]*q
for _ in range(q):
    u,l = map(int,input().split())
 
    m = u.bit_length() - A
    if m<0: m=0
    dv = [0]*(1<<m)
    dw = [0]*(1<<m)
    for i in range(m):
        v,w = vw[u]
        for j in range(1<<i):
            dv[j+(1<<i)] = dv[j]+v
            dw[j+(1<<i)] = dw[j]+w
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            val = memo[u][l-w] + v
            if val > ans: ans = val
    ans_[_] = ans
print(*ans_,sep="\n")

Solution (Python):
import sys


def get_solve():
    cache = [None] * precalc_limit
    cache[0] = [0] * (weight_limit + 1)
    _vvv = vvv
    _www = www
    _weight_limit = weight_limit

    def _f(u):
        """ u < precalc_limit """
        if cache[u] is not None:
            return cache[u]
        dp = _f(u >> 1).copy()
        v = _vvv[u]
        w = _www[u]
        for x in range(_weight_limit, w - 1, -1):
            nv = dp[x - w] + v
            if dp[x] < nv:
                dp[x] = nv
        cache[u] = dp
        return dp

    return _f


n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)

solve = get_solve()

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        dp = solve(u)
        buf.append(dp[l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    dp = solve(u)
    for w, v in zip(dp_w, dp_v):
        nv = v + dp[l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

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

Solution (Python):
import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

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

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())
vw = [(0,0)]+[tuple(map(int,readline().split())) for _ in range(n)]

A = 10
N = min(1<<A,n+1)

memo = [None for _ in range(N)]
L = 10**5+1
memo[0] = [0]*L

for i in range(1,N):
    m = memo[i>>1][:]
    v,w = vw[i]    
    for j in range(L-1,w-1,-1):
        if m[j] < m[j-w]+v:
            m[j] = m[j-w]+v
    memo[i] = m

q, = map(int,readline().split())
ans_ = [0]*q
for _ in range(q):
    u,l = map(int,readline().split())

    m = u.bit_length() - A
    if m<0: m=0
    dv = [0]*(1<<m)
    dw = [0]*(1<<m)
    for i in range(m):
        v,w = vw[u]
        for j in range(1<<i):
            dv[j+(1<<i)] = dv[j]+v
            dw[j+(1<<i)] = dw[j]+w
        u >>= 1
    
    ans = 0
    for v,w in zip(dv,dw):
        if w <= l:
            val = memo[u][l-w] + v
            if val > ans: ans = val
    ans_[_] = ans
    
print(*ans_,sep="\n")

Solution (Python):


def main():
    import sys
    def I(): return int(sys.stdin.readline())
    def LI(): return list(map(int,sys.stdin.readline().split()))

    n = I()
    V = []
    W = []

    maxL = 10**5
    m = min(n, 1 << 10)
    dp = [[0]*(maxL + 1)]
    
    for i in range(n):
        v, w = LI()
        if i <= m:
            d_ = dp[(i+1)>>1][:]
            for j in range(w, maxL+1)[::-1]:
                d_[j] = max(d_[j], d_[j - w] + v)
            dp.append(d_)
        V.append(v)
        W.append(w)
    
    q = I()
    for i in range(q):
        v, L = LI()
        if v <= m:
            print(dp[v][L])
            continue
        cnt = 0
        v_ = []
        w_ = []
        while v > m:
            v_.append(V[v-1])
            w_.append(W[v-1])
            v >>= 1
            cnt += 1
        ret = dp[v][L]
        v_tmp = [0] * (1 << cnt)
        w_tmp = [0] * (1 << cnt)
        for b in range(1, 1 << cnt):
            lsb = b & -b
            l = lsb.bit_length()
            w_t = w_tmp[b - lsb] + w_[l-1]
            w_tmp[b] = w_t
            if w_t <= L:
                v_t = v_tmp[b - lsb] + v_[l-1]
                v_tmp[b] = v_t
                ret = max(ret, v_t + dp[v][L - w_t])
        print(ret)
    return

if __name__ == "__main__":
    main()

Solution (Python):

import sys


def solve():

    input = sys.stdin.buffer.readline
    LI = lambda: map(int, input().split())
    II = lambda: int(input())
    n = II()
    vw = [[]] * n
    M = 10 ** 5 + 1
    M0 = [0] * M
    XX = 1 << 10
    d = [[]] * XX
    d[0] = M0

    for i in range(1, min(XX, n + 1)):
        v, w = LI()
        vw[i - 1] = (v, w)
        di = d[i // 2][:]
        for j in range(M - 1, w - 1, -1):
            if di[j] < di[j - w] + v:
                di[j] = di[j - w] + v
        d[i] = di

    for i in range(XX, n + 1):
        v, w = LI()
        vw[i - 1] = (v, w)

    Vv = [i.bit_length() for i in range(1 << 18)]
    n = [pow(2, i) for i in range(18)]
    lentl = [i - 10 for i in range(19)]
    maskset = [[]] * n[10]

    for i in range(1, 11):
        for mask in range(n[i - 1], n[i]):
            a = mask & -mask
            b = Vv[a] - 1
            maska = mask - a
            maskset[mask - 1] = (mask, b, maska)

    for _ in range(II()):
        V, L = LI()

        if V < XX:
            print(d[V][L])
            continue

        n2 = lentl[Vv[V]]
        vw2 = [None] * n2

        for i in range(n2):
            vw2[i] = (vw[V - 1][0], vw[V - 1][1])
            V //= 2

        lw = [0] * n[n2]
        lv = [0] * n[n2]
        dv = d[V]
        ans = dv[L]

        for i in range(n[n2] - 1):
            mask, b, maska = maskset[i]
            v, w = vw2[b]
            ww = lw[maska] + w
            Lww = L - ww
            lw[mask] = ww
            if Lww < 0: continue
            vv = lv[maska] + v
            lv[mask] = vv
            tmp = dv[Lww] + vv
            if tmp > ans:
                ans = tmp
        print(ans)
    return

if __name__ == "__main__":
    solve()

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline



n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 12
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]


for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    
    
    
    solve(memov[u],memow[u],dv,dw,l)

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline



n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 11
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]


for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    
    
    
    solve(memov[u],memow[u],dv,dw,l)

Solution (Python):
import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys
from numba import njit
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

@njit('(i4,i4[:],i4[:])',cache=True)
def precompute(n,v,w):
    dp = np.zeros((1024,10**5+1),np.int32)
    for i in range(1,min(1024,n+1)):
        vi = v[i]
        wi = w[i]
        p = i//2
        dp[i]=dp[p]
        for j in range(wi,10**5+1):
            dp[i][j] = max(dp[i][j],dp[p][j-wi]+vi)
    return dp

@njit('(i4,i4[:],i4[:],i4[:],i4[:])',cache=True)
def main(n,v,w,vq,lq):
    dp = precompute(n,v,w)
    values = np.empty(1024,np.int32)
    weights = np.empty(1024,np.int32)

    def solve(V,L,values,weights,dp):
        if V < 1024:
            return dp[V][L]
        values[0] = 0
        weights[0] = 0
        p = 0
        while V >= 1024:
            for j in range(1 << p):
                values[j + (1 << p)] = values[j]+ v[V]
                weights[j + (1 << p)] = weights[j] + w[V]
            p += 1
            V >>= 1
        ans = 0
        for i in range(1 << p):
            if weights[i] <= L:
                x = dp[V][L-weights[i]] + values[i]
                ans = max(ans,x)
        return ans
    q = len(vq)
    for i in range(q):
        x = solve(vq[i],lq[i],values,weights,dp)
        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[:2*n:2]
w[1:] = stdin[1:2*n:2]
query = stdin[2*n+1:]
vq = query[::2]
lq = query[1::2]

main(n,v,w,vq,lq)

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


def merge(a, b):
    res = []
    i, j = 0, 0
    while i < len(a) or j < len(b):
        if j >= len(b) or (i < len(a) and a[i][0] < b[j][0]):
            w, v = a[i]
            i += 1
        else:
            w, v = b[j]
            j += 1
        if not res or res[-1][1] < v:
            res.append((w, v))
        elif res[-1][0] == w and res[-1][1] <= v:
            res.pop()
            res.append((w, v))
    return res


def best(L, a, b):
    res = 0
    i = 0
    j = len(b) - 1
    while i < len(a):
        w, v = a[i]
        if j < 0:
            break
        if b[j][0] + w > L:
            j -= 1
            continue
        res = max(res, v + b[j][1])
        i += 1
    return res


def main():
    N = int(input())
    VW = [(-1, -1)] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    query = tuple(tuple(map(int, input().split())) for _ in range(Q))

    dp = [[] for _ in range(2048)]
    dp[0] = [(0, 0)]
    for i in range(1, min(N + 1, 2048)):
        vi, wi = VW[i]
        a1 = dp[i // 2]
        a2 = [(w + wi, v + vi) for w, v in a1]
        dp[i] = merge(a1, a2)

    for n, L in query:
        a = [(0, 0)]
        while n >= 2048:
            vi, wi = VW[n]
            b = [(w + wi, v + vi) for w, v in a]
            a = merge(a, b)
            n //= 2
        print(best(L, a, dp[n]))


if __name__ == "__main__":
    main()

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

    n = int(input())

    L_MAX = 10**5
    D_TH = 10
    V_MAX = (1 << D_TH) - 1
    dp = [[0] * (L_MAX + 1)]
    
    items_v = []
    items_w = []

    for i in range(n):
        val, w = map(int, input().split())
        if i < V_MAX:
            i1 = i + 1
            i0 = (i + 1) >> 1
            dp_ = dp[i0][:]

            
            
            for j in range(w, L_MAX + 1)[::-1]:
                if dp_[j] < dp_[j - w] + val:
                    dp_[j] = dp_[j - w] + val
            dp.append(dp_)
        else:
            
            items_v.append(val)
            items_w.append(w)

    

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

        if v < V_MAX:
            ans = dp[v + 1][l]
        else:
            vv = []
            ww = []
            while v >= V_MAX:
                
                
                vv.append(items_v[v - V_MAX])
                ww.append(items_w[v - V_MAX])
                v = (v - 1) >> 1

            ans = dp[v + 1][l]
            
            m2 = 1 << len(vv)
            v_sub = [0] * m2
            w_sub = [0] * m2
            for bit in range(1, m2):
                bit_min = bit & (-bit)
                x = bit_min.bit_length() - 1

                s_w = w_sub[bit - bit_min] + ww[x]
                w_sub[bit] = s_w
                if s_w <= l:
                    s_val = v_sub[bit - bit_min] + vv[x]
                    v_sub[bit] = s_val
                    ans = max(ans, dp[v + 1][l - s_w] + s_val)

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import bisect
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def merge(a, b):
    res = []
    i, j = 0, 0
    while i < len(a) or j < len(b):
        if j >= len(b) or (i < len(a) and a[i][0] < b[j][0]):
            w, v = a[i]
            i += 1
        else:
            w, v = b[j]
            j += 1
        if not res or (res[-1][1]) < v:
            res.append((w, v))
        elif res[-1][0] == w and res[-1][1] <= v:
            res.pop()
            res.append((w, v))
    return res


def best(L, a, b):
    res = 0
    i = 0
    j = len(b) - 1
    while i < len(a):
        w, v = a[i]
        if j < 0:
            break
        if b[j][0] + w > L:
            j -= 1
            continue
        res = max(res, v + b[j][1])
        i += 1
    return res


def main():
    N = int(input())
    VW = [(-1, -1)] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    query = tuple(tuple(map(int, input().split())) for _ in range(Q))

    dp = [[] for _ in range(2048)]
    dp[0] = [(0, 0)]
    for i in range(1, min(N + 1, 2048)):
        vi, wi = VW[i]
        a1 = dp[i // 2]
        a2 = [(w + wi, v + vi) for w, v in a1]
        dp[i] = merge(a1, a2)

    for n, L in query:
        if n < 2048:
            w, v = zip(*dp[n])
            i = bisect.bisect_right(w, L) - 1
            print(v[i])
        else:
            a = [(0, 0)]
            while n >= 2048:
                vi, wi = VW[n]
                b = [(w + wi, v + vi) for w, v in a]
                a = merge(a, b)
                n //= 2
            print(best(L, a, dp[n]))


if __name__ == "__main__":
    main()

Solution (Python):


import sys
read = sys.stdin.read
readline = sys.stdin.readline



n, = map(int,readline().split())
vw = [[0,0]]+[list(map(int,readline().split())) for _ in range(n)]

def merge(av,aw,bv,bw):
    la,lb = len(aw),len(bw)
    rv = [0]*(la+lb)
    rw = [0]*(la+lb)
    ia = ib = 0
    for i in range(la+lb):
        if ib==lb or (ia < la and aw[ia] < bw[ib]):
            rv[i] = av[ia]
            rw[i] = aw[ia]
            ia += 1
        else:
            rv[i] = bv[ib]
            rw[i] = bw[ib]
            ib += 1
    return rv,rw

A = 10
N = min(1<<A,n+1)
memov = [[] for _ in range(N)]
memow = [[] for _ in range(N)]

memov[0] = [0]
memow[0] = [0]


for i in range(1,N):
    v,w = vw[i]
    m2v = [v+v1 for v1 in memov[i>>1]]
    m2w = [w+w1 for w1 in memow[i>>1]]
    memov[i],memow[i] = merge(memov[i>>1],memow[i>>1],m2v,m2w)

    
    for j in range(1,len(memov[i])):
        memov[i][j] = max(memov[i][j-1],memov[i][j])
    
def solve(lstv,lstw,dv,dw,l):
    ans = 0
    idx = len(lstw)-1
    
    for v,w in zip(dv,dw):
        while idx >= 0 and lstw[idx] + w > l:
            idx -= 1
        if idx >= 0 and v+lstv[idx] > ans:
            ans = v+lstv[idx]
    print(ans)        
 
 

q, = map(int,readline().split())
for _ in range(q):
    u,l = map(int,readline().split())

    dv = [0]
    dw = [0]
    while u >= N:
        v,w = vw[u]
        m2v = [v+v1 for v1 in dv]
        m2w = [w+w1 for w1 in dw]
        dv,dw = merge(dv,dw,m2v,m2w)
        u >>= 1
    
    
    
    
    solve(memov[u],memow[u],dv,dw,l)