Problem:


Score : 700 points

Problem Statement

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N.
Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i.
Now, process the following query Q times:

Given are a vertex v of the tree and a positive integer L.
  Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L.
  Find the maximum possible total value of the chosen items.

Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query.
Then, Input is given from Standard Input in the following format:

N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q

Output

For each integer i from 1 through Q,
the i-th line should contain the response to the i-th query.

Sample Input 1

3
1 2
2 3
3 4
3
1 1
2 5
3 5

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with (V, W)=(1,2). Since L = 1, we cannot actually choose it, so our response should be 0.

In the second query, we are given two choices: the items with (V, W)=(1,2) and (V, W)=(2,3). Since L = 5, we can choose both of them, so our response should be 3.

Sample Input 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

Sample Output 2

256
255
250
247
255
259
223
253



Sample input:
3
1 2
2 3
3 4
3
1 1
2 5
3 5


Sample output:
0
3
3

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [(0, 0)]
W = 0
for i in range(N):
  v, w = map(int, input().split())
  a.append((v, w))
  W += w
#print(a, W)

s = [~1, 1]
order = []
while len(s):
  x = s.pop()
  if x > 0:
    order.append(x)
    if x << 1 <= N:
      s.append(~(x << 1))
      s.append(x << 1)
      s.append(~((x << 1) + 1))
      s.append((x << 1) + 1)
  else: order.append(x)
#print(order)
table = [N * 2 + 1] * (N + 1)
for i in range(N * 2): table[order[i]] = min(table[order[i]], i)
#print(table)
Q = int(input())
qs = [[] for _ in range(N + 1)]
for i in range(Q):
  v, l = map(int, input().split())
  qs[v].append((l, i))
#print(qs)

class SegTree:
  def segfunc(self, x, y):
    return max(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
ln = len(bin(N)) - 2
seg = [SegTree(W + 1, 0, [0] * (W + 1)) for _ in range(ln + 1)]
res = [0] * Q
for x in order:
  if x > 0:
    i = len(bin(x)) - 3
    #print(x, i)
    for j in range(W + 1):
      if j + a[x][0] <= W:
        if seg[i + 1].query(j + a[x][1], j + a[x][1] + 1) < seg[i].query(j, j + 1) + a[x][0]: seg[i + 1].update(j + a[x][1], seg[i].query(j, j + 1) + a[x][0])
      if seg[i + 1].query(j, j + 1) < seg[i].query(j, j + 1): seg[i + 1].update(j, seg[i].query(j, j + 1))
    while len(qs[x]):
      ql, qi = qs[x].pop()
      res[qi] = seg[i + 1].query(0, min(W, ql) + 1)
  else:
    i = len(bin(~x)) - 3
    for j in range(W + 1):
      seg[i + 1].update(j, 0)
  #print(seg[1].seg)
  #print(seg[2].seg)
  #print()
for r in res: print(r)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import defaultdict(int)

sys.setrecursionlimit(10 ** 7)

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

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

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

ul_s = sorted(ul, reverse=True)

cache = [None] * (N + 1)
S = 10 ** 5 + 10
TABLE = defaultdict(int)


def solve(q, l):
    q = q[::-1]

    mi = -1
    for i in range(len(q)):
        x = q[i]
        if type(cache[x]) is np.ndarray:
            mi = i
        else:
            break

    x = q[mi]
    dp = cache[x] if mi != -1 else np.zeros(S, dtype=np.int64)

    q = q[mi + 1 :] if mi != -1 else q
    ans = calc(q, l, dp)
    return ans


def calc(q, l, dp):

    for u in q:
        v, w = VW[u]
        tmp = np.zeros(S, dtype=np.int64)
        tmp[w:] = dp[:-w] + v

        dp = np.maximum(dp, tmp)
        # cache[u] = np.copy(dp)
        cache[u] = dp

    return max(dp[: l + 1])


ans = []
for u, l in ul_s:
    q = []
    v = u
    while v != 1:
        q.append(v)
        v //= 2
    q.append(1)

    t = solve(q, l)
    TABLE[(u,l)] = t

for u, l in ul:
    ans.append(TABLE[(u,l)])


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

Submission status: Runtime Error

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

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

ans = [0]*q

top = set()
mid = set()

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

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

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

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

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

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

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

Submission status: Runtime Error

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

    N = int(input())
    half = (N + 1) // 2 + 1

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

    MAX_W = 10 ** 5 + 1

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

    for i in range(1, half + 1):
        V, W = VW[i - 1][0], VW[i - 1][1]
        for j in range(MAX_W):
            # print (i, j)
            if (j < W):
                dp[i][j] = dp[i // 2][j]
            else:
                dp[i][j] = max(dp[i // 2][j], dp[i // 2][j - W] + V)


    def calc(n, L):
        ans = 0
        lst = []
        while n > half:
            lst.append(n)
            n //= 2
        # print (lst)
        length = len(lst)
        for i in range(2 ** length):
            v = 0
            w = 0
            for j in range(length):
                if ((i >> j) & 1):
                    v += VW[lst[j] - 1][0]
                    w += VW[lst[j] - 1][1]
            if L >= w:
                ans = max(ans, dp[n][L - w] + v) 
        return ans

    Q = int(input())
    for _ in range(Q):
        v, L = map(int, input().split())
        if v > half:
            print (calc(v, L))
        else: #こっち側はOK(当然)
            print (dp[v][L])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [(0, 0)]
W = 0
for i in range(N):
  v, w = map(int, input().split())
  a.append((v, w))
  W += w
#print(a, W)

s = [~1, 1]
order = []
while len(s):
  x = s.pop()
  if x > 0:
    order.append(x)
    if x << 1 <= N:
      s.append(~(x << 1))
      s.append(x << 1)
      s.append(~((x << 1) + 1))
      s.append((x << 1) + 1)
  else: order.append(x)
#print(order)
table = [N * 2 + 1] * (N + 1)
for i in range(N * 2): table[order[i]] = min(table[order[i]], i)
#print(table)
Q = int(input())
qs = [[] for _ in range(N + 1)]
for i in range(Q):
  v, l = map(int, input().split())
  qs[v].append((l, i))
#print(qs)

class SegTree:
  def segfunc(self, x, y):
    return max(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
ln = len(bin(N)) - 2
seg = [SegTree(W + 1, 0, [0] * (W + 1)) for _ in range(ln + 1)]
res = [0] * Q
for x in order:
  if x > 0:
    i = len(bin(x)) - 3
    #print(x, i)
    for j in range(W + 1):
      if j + a[x][0] <= W:
        if seg[i + 1].query(j + a[x][1], j + a[x][1] + 1) < seg[i].query(j, j + 1) + a[x][0]: seg[i + 1].update(j + a[x][1], seg[i].query(j, j + 1) + a[x][0])
      if seg[i + 1].query(j, j + 1) < seg[i].query(j, j + 1): seg[i + 1].update(j, seg[i].query(j, j + 1))
    while len(qs[x]):
      ql, qi = qs[x].pop()
      res[qi] = seg[i + 1].query(0, min(W, ql + 1))
  else:
    i = len(bin(~x)) - 3
    for j in range(W + 1):
      seg[i + 1].update(j, 0)
  #print(seg[1].seg)
  #print(seg[2].seg)
  #print()
for r in res: print(r)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = [(0, 0)]
W = 0
for i in range(N):
  v, w = map(int, input().split())
  a.append((v, w))
  W += w
#print(a, W)

s = [~1, 1]
order = []
while len(s):
  x = s.pop()
  if x > 0:
    order.append(x)
    if x << 1 <= N:
      s.append(~(x << 1))
      s.append(x << 1)
      s.append(~((x << 1) + 1))
      s.append((x << 1) + 1)
  else: order.append(x)
#print(order)
table = [N * 2 + 1] * (N + 1)
for i in range(N * 2): table[order[i]] = min(table[order[i]], i)
#print(table)
Q = int(input())
qs = [[] for _ in range(N + 1)]
for i in range(Q):
  v, l = map(int, input().split())
  qs[v].append((l, i))
#print(qs)

class SegTree:
  def segfunc(self, x, y):
    return max(x, y) #ここ判定関数（ただし結合則があるもの）
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_val
    for i in range(n):
      self.seg[i + self.num - 1] = init_val[i]    
    #built
    for i in range(self.num - 2, -1, -1) :
      self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  def query(self, p, q):
    if q <= p:
      return self.ide_ele
    p += self.num - 1
    q += self.num - 2
    res = self.ide_ele
    while q - p > 1:
      if p & 1 == 0:
        res = self.segfunc(res, self.seg[p])
      if q & 1 == 1:
        res = self.segfunc(res, self.seg[q])
        q -= 1
      p = p // 2
      q = (q - 1) // 2
    if p == q:
      res = self.segfunc(res, self.seg[p])
    else:
      res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
    return res
ln = len(bin(N)) - 2
seg = [SegTree(W + 1, 0, [0] * (W + 1)) for _ in range(ln + 1)]
res = [0] * Q
for x in order:
  if x > 0:
    i = len(bin(x)) - 3
    #print(x, i)
    for j in range(W + 1):
      if j + a[x][0] <= W:
        if seg[i + 1].query(j + a[x][1], j + a[x][1] + 1) < seg[i].query(j, j + 1) + a[x][0]: seg[i + 1].update(j + a[x][1], seg[i].query(j, j + 1) + a[x][0])
      if seg[i + 1].query(j, j + 1) < seg[i].query(j, j + 1): seg[i + 1].update(j, seg[i].query(j, j + 1))
    while len(qs[x]):
      ql, qi = qs[x].pop()
      res[qi] = seg[i + 1].query(0, ql + 1)
  else:
    i = len(bin(~x)) - 3
    for j in range(W + 1):
      seg[i + 1].update(j, 0)
  #print(seg[1].seg)
  #print(seg[2].seg)
  #print()
for r in res: print(r)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np
sys.setrecursionlimit(10 ** 7)

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
VW = [lr() for _ in range(N)]
answer = [None] * (N+1)
dp = np.array([0] * (10 ** 5 + 1))

def dfs(dp, i):
    v, w = VW[i-1]
    next = dp.copy()
    next[w:] = np.maximum(dp[w:], dp[:-w] + v)
    answer[i] = next
    if 2 * i <= N:
        dfs(next, 2*i)
    if 2 * i + 1 <= N:
        dfs(next, 2*i+1)

dfs(dp, 1)
Q = ir()
Z = []
for _ in range(Q):
    v, L = lr()
    Z.append(answer[v][L])

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

def num2bi(x, k):
  out=format(x, '0'+str(k)+'b')
  return out

N=int(input())
V=[0 for _ in range(N+1)]
W=[0 for _ in range(N+1)]
for i in range(N):
  v, w=input().split()
  V[i+1]=int(v)
  W[i+1]=int(w)
  
Q=int(input())
for i in range(Q):
  u, L=input().split()
  u=int(u)
  L=int(L)
  
  dp=defaultdict(int)
  keys=set([0])
  while u>0:
    dptmp={}
    keystmp=set()
    for we in keys:
      tmp=we+W[u]
      if tmp<=L and dp[we]+V[u]>dp[tmp]:
        dptmp[tmp]=dp[we]+V[u]
        keystmp.add(tmp)
    u//=2
    dp.update(dptmp)
    keys=keys|keystmp
    
    
  print(max(dp.values()))

Submission status: Runtime Error

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


# inpt N:number W:maxweight
def solveDP(N, W, value, weight):
    dp = np.zeros((N+1, W+1))
    
    for i in range(N):
        for w in range(W+1):
            if w >= weight[i]:
                dp[i + 1, w] = max(dp[i, w - weight[i]] + value[i], dp[i, w])
            else:
                dp[i + 1, w] = dp[i, w]
    
    return dp[N , W ]

def main():
    """"ここに今までのコード"""
    N = int(input())
    VW = []
    for _ in range(N):
        V, W = map(int, input().split())
        VW.append([V, W])

    VW = np.array(VW).reshape(N,2)
    V = VW[:,0]
    W = VW[:,1]

    Q = int(input())
    vL = []

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

    for vls in vL:
    v, L = vls
    vv = v
    
    value = [V[v - 1]]
    weight = [W[v - 1]]
    
    while vv > 0:
        vv = vv//2
        value.append(V[vv - 1])
        weight.append(W[vv - 1])
    
    # answer
    print(solveDP(len(value),L,value,weight))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
VW = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (10**5 + 1) for _ in range(N + 1)]
for i, (v, w) in enumerate(VW, 1):
    for l in range(10**5 + 1):
        if l < w: dp[i][l] = dp[i//2][l]
        else:
            dp[i][l] = max(dp[i//2][l], dp[i//2][l - w] + v)
Q = int(input())
for _ in range(Q):
    v, L = map(int, input().split())
    print(dp[v][L])

Submission status: Runtime Error

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

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

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


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

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

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

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

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

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

    for v in ans:
        print(v)
    return

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

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

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

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

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

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

Submission status: Runtime Error

Solution code:
N = int(input())
VW = [list(map(int,input().split( ))) for _ in range(N)]
Q = int(input())
vL = [list(map(int,input().split( ))) for _ in range(Q)]
for vLi in vL:
    vi = vLi[0]
    Li = vLi[1] 
    vw = VW[vi-1]
    stock = [(vw[0],vw[1])]
    while vi != 1:
        vi = vi//2
        vw = VW[vi-1]
        stock.append((vw[0],vw[1]))
    V = [0 for _ in range(Li+1)]
    for vi,wi in stock[:-1]:
        for l in range(1,Li+1)[::-1]:
            if l >= wi:
                V[l] = max(V[l],V[l-wi] + vi)
            else:
                V[l] = V[l]
    vi = stock[-1][0]
    wi = stock[-1][1]
    if Li >= wi
    	print(max(V[Li],V[Li-wi] + vi))
    else:
      	print(V[Li])

Submission status: Runtime Error

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

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

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

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

# 前処理　最大2**10まで前計算
b_len = min(11, n.bit_length()-1)

bef = [ [] for _ in range(2**b_len)]
bef[1] = [(0,0),(W[0],V[0])]

for i in range(2,2**b_len):
    iw,iv = W[i-1],V[i-1]
    bef[i] = bef[i//2][::]
    for jw,jv in bef[i//2]:
        bef[i].append((iw+jw,iv+jv))

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

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

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

    aft.sort(reverse=True)

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

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

    ans.append(max_ans)

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

Submission status: Runtime Error

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

import numpy as np
N = int(input())
VW = [list(mapint()) for _ in range(N)]
Q = int(input())

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

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

Submission status: Runtime Error

Solution code:
N = int(input())
VW = [list(map(int,input().split( ))) for _ in range(N)]
Q = int(input())
vL = [list(map(int,input().split( ))) for _ in range(Q)]
for vLi in vL:
    vi = vLi[0]
    Li = vLi[1] 
    vw = VW[vi-1]
    stock = [(vw[0],vw[1])]
    while vi != 1:
        vi = vi//2
        vw = VW[vi-1]
        stock.append((vw[0],vw[1]))
    V = [0 for _ in range(Li+1)]
    for vi,wi in stock[:-1]:
        for l in range(1,Li+1)[::-1]:
            if l >= wi:
                V[l] = max(V[l],V[l-wi] + vi)
            else:
                V[l] = V[l]
    vi = stock[-1][0]
    wi = stock[-1][1]
    print(max(V[Li],V[Li-wi] + vi))

Submission status: Runtime Error

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

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

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


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

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

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

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

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

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

    for v in ans:
        print(v)
    return

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

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

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

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

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

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

Submission status: Runtime Error

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

n = int(input())

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

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

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



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

            while ng - ok > 1:
                mid = (ok+ng)//2
                if a[now][mid][0] > L:
                    ng = mid
                else:
                    ok = mid
            print(a[now][ok][1])
    else:
        print(w[1000000000])