Problem:


Score : 700 points

Problem Statement

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

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

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

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

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

0
3
3

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

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

Sample Input 2

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

Sample Output 2

256
255
250
247
255
259
223
253



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


Sample output:
0
3
3

Submission status: Wrong Answer

Solution code:
import sys
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 = 2 * 10 ** 5
tab = [[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] = l
    tab.append(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)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 11
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))
  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    lknap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      if i == 0:
        left = 0
        right = lknap
      elif wn > ls[i-1][1]:
        if vn < ls[i-1][0]:
          continue
        left = 0
      else:
        right = lknap
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 11
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))
  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    lknap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      if i == 0:
        left = 0
        right = lknap
      elif wn >= ls[i-1][1]:
        if vn <= ls[i-1][0]:
          continue
        left = 0
      else:
        right = lknap
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)

Submission status: Wrong Answer

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


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


half_n = 2 ** (n.bit_length() // 2)

tot1 = [[] for i in range(n)]
tot1[0].append((0, 0))
tot1[0].append((info[0][1], info[0][0]))

for i in range(1, half_n):
    val, wei = info[i]
    for w, v in tot1[(i + 1) // 2 - 1]:
        tot1[i].append((w, v))
        tot1[i].append((w + wei, v + val))
        tot1[i].sort()

for i in range(half_n, n):
    if (i + 1) // 2 - 1 < half_n:
        tot1[i].append((info[i][1], info[i][0]))
        tot1[i].append((0, 0))
    else:
        val, wei = info[i]
        for w, v in tot1[(i + 1) // 2 - 1]:
            tot1[i].append((w, v))
            tot1[i].append((w + wei, v + val))
        tot1[i].sort(reverse=True)


for i, l in query:
    i -= 1
    ans = 0
    if i < half_n:
        for w, v in tot1[i]:
            if w <= l:
                ans = max(ans, v)
        print(ans)
    else:
        ind = i + 1
        while ind > half_n:
            ind //= 2
        ind -= 1
        max_ = 0
        left = 0
        for w, v in tot1[i]:
            while left < len(tot1[ind]):
                w2, v2 = tot1[ind][left]
                if w2 + w > l:
                    break
                max_ = max(max_, v2)
                left += 1
            ans = max(max_ + v, ans)
        print(ans)

Submission status: Wrong Answer

Solution code:
def calc_rec(node):
    do_list=[node]
    while True:
        node//=2
        if node in D.keys():
            break
        else:
            do_list.append(node)
    for node in reversed(do_list):
        new_dp =calc_dp_step(node)
    return new_dp


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

N = int(input())

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

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

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

#DP[weight]=val
D[0]=[0]*Vmax
Q_ans=dict()
for v,L in query:
    if v in D.keys():
        new_dp = D[v]
    if v//2 in D.keys():
        new_dp = calc_dp_step(v)
    else:
        new_dp = calc_rec(v)

    print(max(new_dp[:L+1]))

Submission status: Wrong Answer

Solution code:
import sys

def solve():
    input = sys.stdin.readline
    N = int(input())
    B = [[int(v) for v in input().split()] for _ in range(N)]
    WV = [[] for _ in range(N)]
    Lim = pow(2, 10)
    WV[0].append((0, 0))
    WV[0].append((B[0][1], B[0][0]))
    for i in range(1, min(N, Lim)):
        s = set()
        for w, v in WV[i//2]:
            s |= {(w, v)}
            if w + B[i][1] <= 10 ** 5: s |= {(w + B[i][1], v + B[i][0])}
        WV[i] = sorted(s)
        for j in range(1, len(WV[i])):
            if WV[i][j-1][1] > WV[i][j][1]: WV[i][j] = (WV[i][j][0], WV[i][j-1][1])
    #print(WV)

    Q = int(input())
    Ans = [0] * Q
    for q in range(Q):
        v, L = map(int, input().split())
        add = set()
        add |= {(0, 0)}
        while v >= Lim:
            s = set()
            for w, val in add:
                if w + B[v-1][1] <= L:
                    s |= {(w+B[v-1][1], val + B[v-1][0])}
            add |= s
            v //= 2
        ans = 0
        le = len(WV[v-1])
        for w, val in add:
            low, high = 0, le
            #print(WV[v-1], low, high, le, v-1)
            while high - low > 1:
                mid = (high + low) // 2
                if WV[v-1][mid][0] + w > L: high = mid
                else: low = mid
            ans = max(ans, val + WV[v-1][low][1])
        Ans[q] = ans

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
def calc_rec(node):
    do_list=[node]
    while True:
        node//=2
        if node in D.keys():
            break
        else:
            do_list.append(node)
    for node in reversed(do_list):
        new_dp =calc_dp_step(D[node//2],node)
    return new_dp


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

N = int(input())

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

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

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

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

#DP[val]=weight
D[0]=[Vmax]*Vmax
D[0][0]=0
Q_ans=dict()
for v,L in query_sort:
    if v//2 in D.keys():
        cur_dp = D[v//2]
        new_dp = calc_dp_step(cur_dp,v)
    else:
        new_dp = calc_rec(v)

    tmp_ans=0
    for val in range(Vmax):
        if new_dp[val]<=L:
            tmp_ans = max(tmp_ans,val)
    Q_ans[v]=tmp_ans



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

Submission status: Wrong Answer

Solution code:
def main():
    import bisect
    import collections
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    VW = [tuple(map(int, input().split())) for i in range(N)]

    Q = int(input())

    prev = [0]
    dp = [[]]*(N+1)
    dp[0] = [(0, 0)]
    d = collections.defaultdict(list)
    for i in range(Q):
        v, L = map(int, input().split())
        d[v].append((L, i))

    ans = [0]*Q

    for i in range(1, N+1):
        dp[i] = list(dp[i//2])
        for x, y in dp[i//2]:
            dp[i].append((x + VW[i-1][0], y+VW[i-1][1]))
        dp[i].sort(key=lambda x: (x[1], x[0]))
        tmp = [x[1] for x in dp[i]]
        for x in d[i]:

            id = bisect.bisect_right(tmp, x[0])
            ans[x[1]] = dp[i][id-1][0]

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


main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N=int(input())
MAX_L=10**5
VW=[]
for i in range(N):
    VW.append(list(map(int,input().split())))
Q=int(input())
dp=[[0 for j in range(MAX_L+1)] for i in range(N+1)]
used=[False for i in range(N+1)]

for q in range(Q):
    v,L=map(int,input().split())
    vv=v
    Vs=[]
    while vv>=1:
        Vs.append(vv)
        vv=vv//2
    Vs.reverse()
    
    for i in Vs:
        if used[i]:
            continue
        value,weight=VW[i-1]
        for j in range(MAX_L+1):
            if j-weight>=0:
                dp[i][j]=max(dp[i//2][j-weight]+value,dp[i//2][j])
        used[i]=True
    # print(Vs)
    # print(dp)
    print(dp[v][L])

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

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

d = defaultdict()
li = [-1] * (10**5+10)
li[vw[0][1]] = vw[0][0]
d[0] = li


q = int(input())
for _ in range(q):
    v,l = map(int,input().split())
    li = [v]
    while li[-1] > 1:
        li.append(li[-1]//2)
    li = li[::-1]
    for i,e in enumerate(li):
        if e-1 in d:
            pass
        else:
            tmp = [-1] * (10**5+10)
            d1 = d[li[i-1]-1]
            for j,f in enumerate(d1):
                tmp[vw[e-1][1]] = max(tmp[vw[e-1][1]], vw[e-1][0])
                if f != -1:
                    tmp[j] = d1[j]
                    if j + vw[e-1][1] < 10**5 + 10:
                        tmp[j + vw[e-1][1]] = max(tmp[j + vw[e-1][1]], d1[j] + vw[e-1][0])
            d[e-1] = tmp
    print(max(0, max(d[li[-1]-1][:l+1])))

Submission status: Wrong Answer

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

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

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


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

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

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

            for noww, nowv in candi.items():
                if ne[noww + wc] < nowv + vc:
                    ne[noww + wc] = nowv + vc
            candi = ne
            if s == 0:
                break
            s = V[s]
        half[i] = sorted(candi.items())
    Q = I()
    ans = [0]*Q
    #print(half)
    for q in range(Q):
        s, L = LI()
        s -= 1
        if s<1024:
            cur = 0
            for noww, nowv in half[s]:
                if cur < nowv and noww <= L:
                    cur = nowv
            ans[q] = cur
            continue

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

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

        #print(candi)
        cur = 0
        for noww, nowv in candi.items():
            if cur<nowv and noww<=L:
                l = -1; r = len(half[s])
                while(r-l>1):
                    now = (l+r)//2
                    if half[s][now][0]>L-noww:
                        r = now
                    else:
                        l = now
                if l>=0:
                    x = nowv+half[s][l][1]
                else:
                    x = nowv
                if cur<x:
                    cur = x

        ans[q] = cur


    for v in ans:
        print(v)
    return

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

    ans = 0
    print(ans)
    return

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

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

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

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

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

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from itertools import product
    from operator import itemgetter
    import bisect
    n = int(input())
    vw = [list(map(int, readline().split())) for _ in range(n)]
    q = int(input())

    for _ in range(q):
        v, l = map(int, readline().split())
        nap = []

        while v > 0:
            nap.append(vw[v - 1])
            v //= 2

        num = len(nap)

        nap_first = nap[:(num + 1) // 2]
        nap_second = nap[(num + 1) // 2:]

        set_first = []
        len_nf = len(nap_first)

        for bit in product(range(2), repeat=len_nf):
            cur_v = 0
            cur_w = 0
            for i in range(len_nf):
                if bit[i] == 1:
                    cur_v += nap_first[i][0]
                    cur_w += nap_first[i][1]
            set_first.append((cur_v, cur_w))

        if not set_first:
            set_first.append((0, 0))

        set_second = []
        len_ns = len(nap_second)

        for bit in product(range(2), repeat=len_ns):
            cur_v = 0
            cur_w = 0
            for i in range(len_ns):
                if bit[i] == 1:
                    cur_v += nap_second[i][0]
                    cur_w += nap_second[i][1]
            set_second.append((cur_v, cur_w))

        if not set_second:
            set_second.append((0, 0))

        set_first.sort(key=itemgetter(1))
        set_second.sort(key=itemgetter(1))

        res = 0

        true_first = []

        mx = -1
        for vf, wf in set_first:
            if vf <= mx:
                pass
            else:
                true_first.append((vf, wf))
                mx = vf

        true_second_v = []
        true_second_w = []
        mx = -1
        for vs, ws in set_second:
            if vs <= mx:
                pass
            else:
                true_second_v.append(vs)
                true_second_w.append(ws)
                mx = vs

        res = 0
        for vf, wf in true_first:
            rem = l - wf
            idx = bisect.bisect_left(true_second_w, rem)
            res = max(res, vf + true_second_w[idx-1])

        print(res)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def knapsack(v, l, W, V):
    res = [[0] for i in range(v+1)]
    cos = [[l] for i in range(v+1)]

    for i in range(v):
        for j in range(len(cos[i])):
            if cos[i][j] - W[i] >= 0:
                res[i+1].append(res[i][j] + V[i])
                cos[i+1].append(cos[i][j] - W[i])
    return max(res[-1])

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):
    vv, l = map(int, input().split())
for i in range(Q):
    print(knapsack(vv, l, W, V))

Submission status: Wrong Answer

Solution code:
n=int(input())
wv=[]
for i in range(n):
    wv.append([int(x) for x in input().split()])

q=int(input())
for _ in range(q):
    v,l=[int(x) for x in input().split()]
    opt=[]
    ans=0
    ans2=0
    while v>0:
        opt.append(wv[v-1])
        v=v//2
    #optの全組み合わせループ
    for i in range(2**len(opt)):
        bnr=bin(i)[2:].zfill(len(opt))
        #重さOKの場合
        w=0
        v=0
        cnt=0
        for j in range(len(opt)):
            if bnr[j]=='1':
                w+=opt[j][0]
                v+=opt[j][1]
                cnt+=1
        if w<=l:
            if ans<v:
                ans=v
                ans2=cnt
    print(ans2)

Submission status: Wrong Answer

Solution code:
n = int(input())

from collections import defaultdict

vw = defaultdict(lambda: None)

class Node():
    def __init__(self, index, wei, val):
        self.index = index
        self.wei = wei
        self.val = val
        global vw
        vw[index] = self
        self.dp = defaultdict(int)
        if self.index < 128:
            self.calc()

    def __repr__(self):
        return f'Node({self.index}, {self.wei}, {self.val})'
    @property
    def parent(self):
        if self.index != 1:
            global vw
            return vw[self.index//2]
        
    def calc(self):
        dp = self.dp
        if self.parent is not None:
            pdp = self.parent.dp
            for w, v in list(pdp.items()):
                if v > 0:
                    dp[self.wei+w] = max(self.val+v, pdp[self.wei+w])
            dp[self.wei] = self.val
        else:
            dp[self.wei] = self.val
            
    def search(self, lw):
        ans = 0
        cur = self
        while 1:
            for w, v in cur.dp.items():
                if w <= lw:
                    ans = max(ans, v)
            if cur.index > 1:
                cur = cur.parent
            else:
                break
        return ans

for i in range(1, n+1):
    v, w = map(int, input().split())
    Node(i, w, v)


q = int(input())

for _ in range(q):
    v, l = map(int, input().split())
    print(vw[v].search(l))

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    V = []
    W = []
    for _ in range(N):
        v, w = map(int, input().split())
        V.append(v)
        W.append(w)
    Q = int(input())
    dp = [[0] *(2*10**5) for _ in range(N+1)] # dp[v][w]: vについて、重さw以下の制限を与えた時の最適値。

    que_v = []
    que_l = []
    max_w = [0] * (N+1)
    for _ in range(Q):
        v, l = map(int, input().split())
        que_v.append(v)
        que_l.append(l)
        while v != 0:
            max_w[v] = max(max_w[v], l)
            v //= 2
    for v in range(1, N+1):
        par = v // 2
        for w in range(1,10**5+1):
            if w > max_w[v]:
                break
            if w-W[v-1] >= 0:
                dp[v][w] = max(dp[par][w], dp[par][w-W[v-1]]+V[v-1])
    for i in range(Q):
        v, l = que_v[i], que_l[i]
        print(dp[v][l])


        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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(len(wv).bit_length() - i.bit_length()):
        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[0][1], VW[0][0])], 1)
print(*ans, sep='\n')

Submission status: Wrong Answer

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

    N = int(input())
    half = min(2 ** 9, N)

    VW = [tuple(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(W):
            dp[i][j] = dp[i // 2][j]
        if j in range(W, MAX_W):
            dp[i][j] = max(dp[i // 2][j], dp[i // 2][j - W] + V)


    def calc(n, L):
        ans = 0
        lst = []
        lst_append = lst.append
        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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
vw = [[0,0]]+[list(map(int,input().split())) for i in range(n)]
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]
border = 11
knapls = [[] for i in range(2**border)]
knapls[0].append((0,0))
for i in range(1,2**border):
  ls = []
  if i > n:
    break
  ls.extend(knapls[i//2])
  v,w = vw[i]
  l = len(ls)
  for j in range(l):
    vp,wp = ls[j]
    if wp+w > 10**5:
      continue
    ls.append((vp+v,wp+w))
  ls.sort(key = lambda x:x[1])
  knapls[i].append((0,0))
  for j in range(len(ls)):
    vn,wn = ls[j]
    vp,wp = knapls[i][-1]
    if wp <= wn and vp >= vn:
      continue
    knapls[i].append(ls[j])
for v,L in query:
  if v >= 2**border:
    anc = v
    ls = [(0,0)]
    while anc >= 2**border:
      vn,wn = vw[anc]
      l = len(ls)
      for i in range(l):
        vp,wp = ls[i]
        if wp+wn > L:
          continue
        ls.append((vp+vn,wp+wn))
      anc //= 2
    ans = 0
    l = len(ls)
    lnap = len(knapls[anc])
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = lnap
      if wn >= ls[i-1][1] and vn <= ls[i-1][0]:
        continue
      while left+1 < right:
        mid = (left+right)//2
        if knapls[anc][mid][1] > rest:
          right = mid
        else:
          left = mid
      ans = max(knapls[anc][left][0]+vn,ans)
    print(ans)
  else:
    ans = 0
    left = 0
    right = len(knapls[v])
    while left+1 < right:
      mid = (left+right)//2
      if knapls[v][mid][1] > L:
        right = mid
      else:
        left = mid
    ans = knapls[v][left][0]
    print(ans)

Submission status: Wrong Answer

Solution code:
N = int(input())
point = [[0 for weight in range(10**7)] for tree in range(N)]
maW = [0 for k in range(N)]
for k in range(N):
    V, W = map(int, input().split())
    point[k][W + maW[max((k-1)//2+1, 0)] -1] = V + point[k//2][maW[max((k-1)//2, 0)]-1] #maxの更新
    for n in range(W-1, W + maW[max((k-1)//2, 0)]-1):
        point[k][n] = max(V + point[k//2][n - W], point[k//2][n]) #min-maxの更新
    for j in range(maW[max((k-1)//2, 0)], W):
        point[k][j-1] = point[k//2][maW[max((k-1)//2, 0)]-1]
    maW[k] = maW[max((k-1)//2, 0)] + W
    print(point)
    print(maW)

Q = int(input())
for k in range(Q):
    v, L = map(int, input().split())
    print(max(point[v-1][:L]))

Submission status: Wrong Answer

Solution code:
"""

"""
import copy
N = int(input())
items = [list(map(int,input().split())) for _ in range(N)]
Q = int(input())
query = [list(map(int,input().split())) for _ in range(Q)]

maxL = max(query,key=lambda x: x[1])[1]
dp = [[0]*(maxL+1) for _ in range(N+1)]

for i in range(1,N+1):
    v,w = items[i-1]
    p = i//2
    for j in range(maxL+1):
        if j-w>=0:
            dp[i][j] = max(dp[p][j],dp[p][j-w]+v)

for u,l in query:
    print(dp[u][l])

Submission status: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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


lst=[0]*(n+1)
dic={}
dic[0]=0
lst[0]=dic
for i in range(n):
    V,W=VW[i]
    dic=copy.deepcopy(lst[(i+1)//2])
    # print(i,dic)
    for j in list(dic.keys()):
        if not j+W in dic:
            dic[j+W]=dic[j]+V
        else:
            dic[j+W]=max(dic[j+W],dic[j]+V)
    lst[i+1]=dic
    # print(lst)
# print(lst)

for i in range(q):
    v,L=vL[i]
    tmp=list(lst[v].keys())
    tmp.sort()
    tmp2=bisect.bisect(tmp,L)
    # print(tmp,tmp2,L)
    print(lst[v][tmp[tmp2-1]])