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: Time Limit Exceeded

Solution code:
import bisect
import os
from collections import defaultdict

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# ガウス記号！おぼえた

N = int(sys.stdin.buffer.readline())
VW = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
Q = int(sys.stdin.buffer.readline())
VL = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

VW = [(0, 0)] + VW
D = N.bit_length()
queries = defaultdict(list)

for i, (v, l) in enumerate(VL):
    queries[v].append((l, i))
ans = [-1] * Q
cnt = 0

def solve(wv, i, depth):
    # global cnt
    # cnt +=1
    # print(cnt,i,flush=True)

    children = [i]
    if depth == MAX_D:
        for j in range(1, D):
            for v in range(i << j, (i + 1) << j):
                if v > N:
                    break
                children.append(v)

    wv1 = []
    prev_v = -INF
    for w, v in sorted(wv):
        v = max(prev_v, v)
        wv1.append((w, v))
        prev_v = v

    for i in children:
        if not queries[i]:
            continue
        wva = []
        for j in range(i.bit_length() - len(wv1).bit_length() + 1):
            wva.append((VW[i >> j][1], VW[i >> j][0]))

        wv = []
        for choices in itertools.product([True, False], repeat=len(wva)):
            ws, vs = 0, 0
            for j, (w, v) in enumerate(wva):
                if choices[j]:
                    ws += w
                    vs += v
            wv.append((ws, vs))

        wv2 = []
        prev_v = -INF
        for w, v in sorted(wv):
            v = max(prev_v, v)
            wv2.append((w, v))
            prev_v = v

        for ql, qi in queries[i]:
            ret = 0
            for w2, v2 in wv2:
                idx = bisect.bisect_left(wv1, (ql - w2 + 1, -INF)) - 1
                if idx >= 0:
                    ret = max(ret, wv1[idx][1] + v2)
            ans[qi] = ret


def dfs(d, wv, p):
    if p > N:
        return
    solve(wv, p, d)
    if d >= MAX_D:
        return
    for i in (p << 1, (p << 1) + 1):
        if i > N:
            break
        next_wv = []
        for w, v in wv:
            next_wv.append((w + VW[i][1], v + VW[i][0]))
        dfs(d + 1, wv + next_wv, i)


MAX_D = min(9, N.bit_length() - 1)
dfs(1, [(0, 0), (VW[1][1], VW[1][0])], 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
INF = float("inf")


def main():
    # 事前にDPする。必ず上からDPする
    # すでに計算済みのところはスキップする
    # N*Lの配列を用意するとダメなので、
    # 辞書で対応したい。要素数は高々log(N)だと思う。
    # 頂点ごとに辞書を持つことになる。
    N = int(input())
    V = [-1]
    W = [-1]
    for i in range(N):
        a, b = map(int, input().split())
        V.append(a)
        W.append(b)

    Q = int(input())
    v = []
    L = []
    for i in range(Q):
        a, b = map(int, input().split())
        v.append(a)
        L.append(b)

    LMAX = max(L)

    DP = [None]*(N+1)

    for q in range(Q):
        order = []
        while v[q] > 0:
            order.append(v[q])
            v[q] >>= 1

        pre = None
        for u in reversed(order):
            if DP[u] is None:
                # 重さがkeyになるときの価値の総和value
                if pre is None:
                    DP[u] = {0: 0, W[u]: V[u]}
                else:
                    DP[u] = pre.copy()
                    a = sorted(pre.keys(), reverse=True)
                    for k in a:
                        DP[u][k+W[u]] = pre[k]+V[u]
                        if k+W[u] in pre:
                            DP[u][k+W[u]] = max(DP[u][k+W[u]], pre[k+W[u]])
            pre = DP[u]
        # key
        # DP[order[0]]のうち、L[q]以下のもので最大のもの
        # print(DP[order[0]])
        m = 0
        for k, val in DP[order[0]].items():
            if k <= L[q]:
                m = max(m, val)
        # print(DP[order[0]//2])
        # print(DP[order[0]])
        print(m)

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

def solve_dp(l_max):
    dp = [[0] * (l_max + 1) for _ in  range(2 ** k)]
    for i in range(1, 2 ** k):
        for j in range(l_max + 1):
            if j >= weight[i]:
                dp[i][j] = max(dp[i//2][j], 
                               dp[i//2][j-weight[i]] + value[i])
            else:
                dp[i][j] = dp[i//2][j]
    return dp


n = int(input())
k = (n-1).bit_length() // 2
value = [-1]
weight = [-1]
for _ in range(n):
    v, w = map(int, input().split())
    value.append(v)
    weight.append(w)

q = int(input())
query_v, query_l = [], []
for _ in range(q):
    v, l = map(int, input().split())
    query_v.append(v)
    query_l.append(l)

# 木全体の半分の深さまでdpテーブルを作っておく
l_max = max(query_l)
dp = solve_dp(l_max)

# 残りの半分についてはクエリ毎に処理
for v, l in zip(query_v, query_l):
    if v < 2 ** k:
        print(dp[v][l])
        continue

    indices = []
    tmp = v
    while tmp >= 2 ** k:
        indices.append(tmp)
        tmp //= 2
    
    ans = 0
    for item in itertools.product([0, 1], repeat=len(indices)):
        v_sum, w_sum = 0, 0
        for i, idx in zip(item, indices):
            if i:
                v_sum += value[idx]
                w_sum += weight[idx]
        if w_sum > l:
            continue
        ans = max(ans, v_sum + dp[tmp][l-w_sum])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    vw = [list(map(int, input().split())) for _ in range(n)]

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [[0] * ma for _ in range(n2)]
    for i in range(vw[0][1], ma):
        tab[0][i] = vw[0][0]

    for i in range(1, n2):
        j = (i - 1) // 2
        l = 0
        aa, bb = vw[i]
        a = tab[j]
        b = tab[i]
        for k in range(bb):
            b[k] = a[k]
        for k in range(bb, ma):
            l = max((l, a[k - bb] + aa, a[k]))
            b[k] = l

    q = int(input())
    for _ in range(q):
        u, l = map(int, input().split())
        u -= 1
        if u < n2:
            print(tab[u][l])
        else:
            a = [(0, 0)]
            while u >= n2:
                for i in a[:]:
                    if i[0] + vw[u][1] <= l:
                        a.append((i[0] + vw[u][1], i[1] + vw[u][0]))
                u = (u - 1) // 2
            ans = 0
            b = tab[u]
            for i, j in a:
                ans = max(ans, b[l - i] + j)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
M = 10 ** 5 + 1
K = 10
A = [(0, 0)] * max(N + 1, 1 << K)
X = [[], [-1] * M]
X[1][0] = 0
v, w = map(int, input().split())
X[1][w] = v
A[1] = (v, w)
for i in range(2, min(N + 1, 1 << K)):
    v, w = map(int, input().split())
    if i % 2 == 0:
        X.append(X[i // 2][:])
    else:
        X.append([])
        X[i] = X[i // 2]
    
    for j in range(w, M)[::-1]:
        if X[i][j-w] >= 0:
            X[i][j] = max(X[i][j], X[i][j-w] + v)
    
    A[i] = (v, w)

for i in range(1 << K, N + 1):
    v, w = map(int, input().split())
    A[i] = (v, w)

if len(X) < 1 << K:
    for i in range(len(X), 1 << K):
        X.append([-1] * M)

for i in range(1 << K - 1, 1 << K):
    for j in range(1, M):
        X[i][j] = max(X[i][j], X[i][j-1])

Q = int(input())
for _ in range(Q):
    i, maw = map(int, input().split())
    if i < 1 << K - 1:
        V = []
        W = []
        while i:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        k = len(V)
        ma = 0
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, vv)
        print(ma)
    else:
        V = []
        W = []
        while i >= 1 << K:
            v, w = A[i]
            V.append(v)
            W.append(w)
            i //= 2
        ii = i
        k = len(V)
        WW = [0] * (1 << k)
        VV = [0] * (1 << k)
        ma = X[ii][maw]
        for i in range(1, 1 << k):
            a = i & (-i)
            b = a.bit_length() - 1
            ww = WW[i-a] + W[b]
            WW[i] = ww
            if ww > maw: continue
            vv = VV[i-a] + V[b]
            VV[i] = vv
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    vw = [list(map(int, input().split())) for _ in range(n)]

    n2 = max(1, min(n, int(n ** 0.33333)))

    ma = 10 ** 5 + 1
    tab = [[0] * ma for _ in range(n2)]
    for i in range(vw[0][1], ma):
        tab[0][i] = vw[0][0]

    for i in range(1, n2):
        j = (i - 1) // 2
        l = 0
        aa, bb = vw[i]
        for k in range(bb):
            tab[i][k] = tab[j][k]
        for k in range(bb, ma):
            l = max((l, tab[j][k - bb] + aa, tab[j][k]))
            tab[i][k] = l

    q = int(input())
    for _ in range(q):
        u, l = map(int, input().split())
        u -= 1
        if u < n2:
            print(tab[u][l])
        else:
            a = [(0, 0)]
            while u >= n2:
                for i in a[:]:
                    if i[0] + vw[u][1] <= l:
                        a.append((i[0] + vw[u][1], i[1] + vw[u][0]))
                u = (u - 1) // 2
            ans = 0
            for i, j in a:
                ans = max(ans, tab[u][l - i] + j)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

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

    ans.append(max_ans)

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    vw = [list(map(int, input().split())) for _ in range(n)]

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [0 for _ in range(n2)]
    tab[0] = [0] * ma
    for i in range(vw[0][1], ma):
        tab[0][i] = vw[0][0]

    for i in range(1, n2):
        j = (i - 1) // 2
        a = tab[j][:]
        l = 0
        aa, bb = vw[i]
        for k in range(bb, ma):
            l = max((l, tab[j][k - bb] + aa, a[k]))
            a[k] = l
        tab[i] = a

    q = int(input())
    for _ in range(q):
        u, l = map(int, input().split())
        u -= 1
        if u < n2:
            print(tab[u][l])
        else:
            a = [(0, 0)]
            while u >= n2:
                for i in a[:]:
                    if i[0] + vw[u][1] <= l:
                        a.append((i[0] + vw[u][1], i[1] + vw[u][0]))
                u = (u - 1) // 2
            ans = 0
            for i, j in a:
                ans = max(ans, tab[u][l - i] + j)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from numba import jit

@jit
def main(M,N,Q,V,W,v,L):
    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)
    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    for i in range(Q):
        n,l = v[i],L[i]
        ans = 0
        if n < M:
            ans = dp[n][l]
        else:
            vl = []
            while n >= M:
                vl.append(n)
                n //= 2
            m = len(vl)
            ans = dp[vl[-1]//2][l]
            for n in range(2**m):
                v_tot = 0
                w_tot = 0
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[vl[k]-1]
                        w_tot += W[vl[k]-1]
                if w_tot <= l:
                    ans = max(ans,v_tot+dp[vl[-1]//2][l-w_tot])
        print(ans)

M = 2**9
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())
v = []
L = []
for i in range(Q):
    vL = list(map(int,input().split()))
    v.append(vL[0])
    L.append(vL[1])
main(M,N,Q,V,W,v,L)

Submission status: Time Limit Exceeded

Solution code:
#from __future__ import division

import sys
class Knapsack:
    def __init__(self, VW):
        self.VW = VW
        self.VW.sort(key=lambda vw: vw[0] / vw[1], reverse=True)
        self.n = len(VW)
 
    def solve(self, capacity):
        self.capacity = capacity
        self.ok = self._greedy()
        return self._dfs(0, 0, 0)
 
    def _greedy(self):
        capacity = self.capacity
        res = 0
        for v, w in self.VW:
            if w <= capacity:
                res += v
                capacity -= w
        return res
 
    def _dfs(self, depth, s0, s1):
        ng, f = self._solve_relaxation(s0, s1)
        if f == -1:
            self.ok = max(self.ok, ng)
            return ng
        if ng < self.ok:
            return -float("inf")
        res = -float("inf")
        res = max(res, self._dfs(depth+1, s0 | 1<<f, s1))
        res = max(res, self._dfs(depth+1, s0, s1 | 1<<f))
        return res
 
    def _solve_relaxation(self, s0, s1):
        f = -1
        res = 0
        capacity = self.capacity
        for i, (v, w) in enumerate(self.VW):
            if s1 >> i & 1:
                res += v
                capacity -= w
        if capacity < 0:
            return -float("inf"), f
        forbidden = s0 | s1
        for i, (v, w) in enumerate(self.VW):
            if forbidden >> i & 1:
                continue
            if capacity == 0:
                break
            if w <= capacity:
                capacity -= w
                res += v
            else:
                f = i
                res += v * (capacity / w)
                break
        return res, f

def main():
    input = sys.stdin.readline
    N = int(input())
    VW = [0] + [list(map(int, input().split())) for _ in range(N)]
    Q = int(input())
    Ans = []
    for _ in range(Q):
        V, L = map(int, input().split())
        vw = []
        while V > 0:
            vw.append(VW[V])
            V //= 2
        knapsack = Knapsack(vw)
        ans = knapsack.solve(L)
        Ans.append(ans)
    print("\n".join(map(str, Ans)))

main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

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

#print(vw)
A = 11
N = min(1<<A,n+1)

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

from itertools import accumulate

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] = list(accumulate(m,max))


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

    dic = [(0,0)]
    while u >= N:
        dic += [(vw[u][1]+w1,vw[u][0]+v1) for w1,v1 in dic]
        u >>= 1
    
    ans = 0
    for w,v in dic:
        if w <= l:
            ans = max(ans,memo[u][l-w]+v)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from numba import njit

@njit
def main(M,N,Q,V,W,v,L):
    dp = [[0]*(10**5+1) for _ in range(min(M,N+1))]

    for n in range(1,min(M,N+1)):
        for l in range(10**5+1):
            c = 0
            if l>=W[n-1]:
                c = dp[n//2][l-W[n-1]]+V[n-1]
            dp[n][l] = max(dp[n//2][l],c)
    for n in range(min(M,N+1)):
        for l in range(1,10**5+1):
            dp[n][l] = max(dp[n][l],dp[n][l-1])

    for i in range(Q):
        n,l = v[i],L[i]
        ans = 0
        if n < M:
            ans = dp[n][l]
        else:
            vl = []
            while n >= M:
                vl.append(n)
                n //= 2
            m = len(vl)
            ans = dp[vl[-1]//2][l]
            for n in range(2**m):
                v_tot = 0
                w_tot = 0
                for k in range(m):
                    if 2**k&n==2**k:
                        v_tot += V[vl[k]-1]
                        w_tot += W[vl[k]-1]
                if w_tot <= l:
                    ans = max(ans,v_tot+dp[vl[-1]//2][l-w_tot])
        print(ans)

M = 2**10
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())
v = []
L = []
for i in range(Q):
    vL = list(map(int,input().split()))
    v.append(vL[0])
    L.append(vL[1])
main(M,N,Q,V,W,v,L)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
V = [None]*n
W = [None]*n
for i in range(n):
    V[i],W[i] = map(int, input().split())

from queue import deque
q = deque([0])
d = [None]*n
d[0] = [(0,0), (W[0], V[0])]

until = min(n, 2**12-1)

# until = n
while q:
    u = q.pop()
    l = d[u]
    for v in (2*u+1, 2*u+2):
        if v>=until:
            continue
        ll = l + list((ww+W[v], vv+V[v]) for ww,vv in l)
        ll.sort()
        tmp = [ll[0]]
        for item in ll:
            if tmp[-1][1]<item[1]:
                tmp.append(item)
                
        d[v] = tmp
        q.appendleft(v)

from bisect import bisect_right as br
def sub(vv, L):
    if d[vv] is None:
        ll = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll.extend(list((wt+W[vv], vt+V[vv]) for wt,vt in ll))
        ll.sort()
        tmp = [ll[0]]
        for item in ll:
            if tmp[-1][1]<item[1]:
                tmp.append(item)
        tmp = ll
    else:
        tmp = [(0,0)]
    l = d[vv]
    ans = -1
    
    for w1,v1 in tmp:
        if w1>L:
            continue
        out = br(l, (L-w1, float("inf")))
        ans = max(ans, l[out-1][1]+v1)
    return ans
        
q = int(input())
ans = [None]*q
for i in range(q):
    vv, ll = map(int, input().split())
    vv -= 1
    ans[i] = sub(vv, ll)
write("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

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

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

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

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

    for _ in range(Q):

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import os
from collections import defaultdict

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# ガウス記号！おぼえた

N = int(sys.stdin.buffer.readline())
VW = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
Q = int(sys.stdin.buffer.readline())
VL = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

VW = [(0, 0)] + VW
D = N.bit_length()
queries = defaultdict(list)

for i, (v, l) in enumerate(VL):
    queries[v].append((l, i))
ans = [-1] * Q


def solve(wv, i):
    if not queries[i]:
        return

    wv1 = []
    prev_v = -INF
    for w, v in sorted(wv):
        v = max(prev_v, v)
        wv1.append((w, v))
        prev_v = v

    wva = []
    for j in range(i.bit_length() - len(wv).bit_length() + 1):
        wva.append((VW[i >> j][1], VW[i >> j][0]))

    wv = []
    for choices in itertools.product([True, False], repeat=len(wva)):
        ws, vs = 0, 0
        for j, (w, v) in enumerate(wva):
            if choices[j]:
                ws += w
                vs += v
        wv.append((ws, vs))

    wv2 = []
    prev_v = -INF
    for w, v in sorted(wv):
        v = max(prev_v, v)
        wv2.append((w, v))
        prev_v = v

    for ql, qi in queries[i]:
        ret = 0
        for w2, v2 in wv2:
            idx = bisect.bisect_left(wv1, (ql - w2 + 1, -INF)) - 1
            if idx >= 0:
                ret = max(ret, wv1[idx][1] + v2)
        ans[qi] = ret


def dfs(d, wv, p):
    if p > N:
        return
    solve(wv, p)
    for i in (p << 1, (p << 1) + 1):
        if i > N:
            break
        if d < MAX_D:
            next_wv = []
            for w, v in wv:
                next_wv.append((w + VW[i][1], v + VW[i][0]))
            dfs(d + 1, wv + next_wv, i)
        else:
            dfs(d + 1, wv, i)


MAX_D = 9
dfs(1, [(0, 0), (VW[1][1], VW[1][0])], 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import bisect
import os
from collections import defaultdict

import itertools
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

# ガウス記号！おぼえた

N = int(sys.stdin.buffer.readline())
VW = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]
Q = int(sys.stdin.buffer.readline())
VL = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

VW = [(0, 0)] + VW
D = N.bit_length()
queries = defaultdict(list)

for i, (v, l) in enumerate(VL):
    queries[v].append((l, i))
ans = [-1] * Q


def solve(wv, i):
    if not queries[i]:
        return

    wv1 = []
    prev_v = -INF
    for w, v in sorted(wv):
        v = max(prev_v, v)
        wv1.append((w, v))
        prev_v = v

    wva = []
    for j in range(i.bit_length() - len(wv).bit_length() + 1):
        wva.append((VW[i >> j][1], VW[i >> j][0]))

    wv = []
    for choices in itertools.product([True, False], repeat=len(wva)):
        ws, vs = 0, 0
        for j, (w, v) in enumerate(wva):
            if choices[j]:
                ws += w
                vs += v
        wv.append((ws, vs))

    wv2 = []
    prev_v = -INF
    for w, v in sorted(wv):
        v = max(prev_v, v)
        wv2.append((w, v))
        prev_v = v

    for ql, qi in queries[i]:
        ret = 0
        for w2, v2 in wv2:
            idx = bisect.bisect_left(wv1, (ql - w2 + 1, -INF)) - 1
            if idx >= 0:
                ret = max(ret, wv1[idx][1] + v2)
        ans[qi] = ret


def dfs(d, wv, p):
    if p > N:
        return
    solve(wv, p)
    for i in (p << 1, (p << 1) + 1):
        if i > N:
            break
        if d <= MAX_D:
            next_wv = []
            for w, v in wv:
                next_wv.append((w + VW[i][1], v + VW[i][0]))
            dfs(d + 1, wv + next_wv, i)
        else:
            dfs(d + 1, wv, i)


MAX_D = 9
dfs(1, [(0, 0), (VW[1][1], VW[1][0])], 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def calc_dp_step(node_id):
    cur_dp = D[node_id//2]
    (node_val,node_weight) = nodes[node_id]

    new_dp=[0]*Vmax
    for j in range(Vmax):
        if j < node_weight: 
            new_dp[j] = cur_dp[j]
        else:
            new_dp[j] = max(cur_dp[j],cur_dp[j-node_weight]+node_val)
    D[node_id]=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)]

D=dict()
Vmax=10**5+1

#DP[weight]=val
D[0]=[0]*Vmax
Q_ans=dict()
for i in range(1,(N+2)//2+1):
    calc_dp_step(i)

for v,L in query:
    cur_val,cur_weight = nodes[v]
    if L-cur_weight>=0:
        print(max(D[v//2][L],D[v//2][L-cur_weight]+cur_val))
    else:
        print(D[v//2][L])

Submission status: Time Limit Exceeded

Solution code:
import sys


def main():
    input = sys.stdin.readline
    n = int(input())
    wv = []
    for _ in range(n):
        v, w = map(int, input().split())
        wv.append((w, v))

    n2 = max(1, min(n, int(n ** 0.5)))

    ma = 10 ** 5 + 1
    tab = [0 for _ in range(n2)]
    tab[0] = [0] * ma
    for i in range(wv[0][0], ma):
        tab[0][i] = wv[0][1]

    for i in range(1, n2):
        j = (i - 1) // 2
        a = tab[j][:]
        l = 0
        for k in range(wv[i][0], ma):
            l = max((l, tab[j][k - wv[i][0]] + wv[i][1], a[k]))
            a[k] = l
        tab[i] = a

    q = int(input())
    for _ in range(q):
        u, l = map(int, input().split())
        u -= 1
        if u < n2:
            print(tab[u][l])
        else:
            a = [(0, 0)]
            while u >= n2:
                for i in a[:]:
                    if i[0] + wv[u][0] <= l:
                        a.append((i[0] + wv[u][0], i[1] + wv[u][1]))
                u = (u - 1) // 2
            ans = 0
            for i, j in a:
                ans = max(ans, tab[u][l - i] + j)
            print(ans)


if __name__ == "__main__":
    main()