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

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

def main():
    n=II()
    vv=[]
    ww=[]
    for _ in range(n):
        v,w=MI()
        vv.append(v)
        ww.append(w)
    q=II()
    ii=[-1]*n
    mm=[-1]*n
    for i in range(q):
        u,m=MI()
        ii[u-1]=i
        mm[u-1]=m
    ans=[-1]*q

    def dfs(u,dp):
        ndp=dp.copy()
        vu=vv[u]
        wu=ww[u]
        for w,v in dp.items():
            nw=w+wu
            if nw>200005:continue
            nv=v+vu
            if nw in ndp:ndp[nw]=max(ndp[nw],nv)
            else:ndp[nw]=nv
        if ii[u]!=-1:
            i=ii[u]
            m=mm[u]
            ans[i]=max(v for w,v in ndp.items() if w<=m)
        if 2*u+1<n:dfs(2*u+1,ndp)
        if 2*u+2<n:dfs(2*u+2,ndp)

    dfs(0,{0:0})

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

main()

Submission status: Wrong Answer

Solution code:
N=int(input())

I=[]
for i in range(N):
    v,w=map(int, input().split())
    I.append((v,w))

Q=int(input())
for i in range(Q):
    v,l=map(int, input().split())
    L=[v-1]
    while v>1:
      v=v//2
      L.append(v-1)
    dp=[[0]*(l+1) for _ in range(len(L)+1)]
    #print(L)
    #iばんめのアイテム
    #limit==j
    for i in range(1,len(L)+1):
        for j in range(l+1):
            idx=L[i-1]
            w=I[idx][1]
            v=I[idx][0]
            if j-w>=0:
                #print(i,j)
                dp[i][j]=max(dp[i-1][j], dp[i-1][j-w]+v)
    #print(dp, L,l)
    print(dp[len(L)][l])

Submission status: Wrong Answer

Solution code:
def calc_rec(node):
    if node//2 in D.keys():
        return calc_dp_step(D[node//2],node)
    else:
        return calc_dp_step(calc_rec(node//2),node)

def calc_dp_step(cur_dp,node_id):
    (node_val,node_weight) = nodes[node_id]
    new_dp=[10**5]*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

D[0]=[10**5]*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)
    for j in reversed(range(Vmax)):
        if new_dp[j]<=L:
            Q_ans[v]=j
            break

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

Submission status: Wrong Answer

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**12まで前計算
b_len = min(12, 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: Wrong Answer

Solution code:
import math
N = int(input())
vw = [0] * N
for i in range(N):
  vw[i] = list(map(int, input().split()))
  
def knap(v, L):
  x = int(math.log(v, 2)) + 1
  dp = [[0] * (L + 1) for i in range(x + 1)]
  i = 0
  while v >= 1:
    now = vw[v - 1]
    for j in range(1, L + 1):
      if j - now[1] >= 0: 
        dp[i + 1][j] = max(dp[i][j - now[1]] + now[0], dp[i][j])
    i += 1
    v = int(v / 2)
    #print(v, x)
    #print(dp)
  return dp[x][L]

Q = int(input())
for i in range(Q):
  v, L = map(int, input().split())
  print(knap(v, L))

Submission status: Wrong Answer

Solution code:
def calc_rec(node):
    if node//2 in D.keys():
        return calc_dp_step(D[node//2],node)
    else:
        return calc_dp_step(calc_rec(node//2),node)

def calc_dp_step(cur_dp,node_id):
    (node_val,node_weight) = nodes[node_id]
    new_dp=[10**5]*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

D[0]=[10**5]*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]
    else:
        cur_dp = calc_rec(v)
    new_dp = calc_dp_step(cur_dp,v)
    for j in reversed(range(Vmax)):
        if new_dp[j]<=L:
            Q_ans[v]=j
            break

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

Submission status: Wrong Answer

Solution code:
N = int(input())
u = [[]]
for _ in range(N):
    V,W = map(int,input().split())
    u.append((V,W))
#print(u)
Query = int(input())
Knapsack = []
for _ in range(Query):
    v,L = map(int,input().split())
    Knapsack.append((v,L))
for v,L in Knapsack:
    q = {}
    while v>=1:
        q[u[v][0]]=u[v][1]
        v //=2
    dp = [0 for _ in range(L+1)]
    va_q = sorted(q,reverse=True)
    for k,va in q.items():
        for w in range(L+1):
            if w-va>=0:
                if dp[w]<dp[w-va]+k:
                    dp[w]=dp[w-va]+k
    #print(dp)
    print(max(dp))

Submission status: Wrong Answer

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**14-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:
        tmp = [(0,0), (W[vv], V[vv])]
        while d[vv] is None:
            vv = (vv-1)//2
            ll = tmp + list((wt+W[vv], vt+V[vv]) for wt,vt in tmp)
            ll.sort()
            tmp = [ll[0]]
            for item in ll:
                if tmp[-1][1]<item[1]:
                    tmp.append(item)
            ll = tmp
    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: 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)]
dp[0][0] = 0

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

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
lines = sys.stdin.readlines()

#N = int(input())
#VW = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#Q = int(input())
#vL = [list(map(int,input().split())) for i in range(Q)]
#vs,Ls = zip(*vL)

N = int(lines[0])
Q = int(lines[N+1])
vL = [list(map(int,s.split())) for s in lines[N+2:]]
vs,Ls = zip(*vL)
VW = {}

appear = []
for v in vs:
    v *= 2
    while v:
        v //= 2
        appear.append(v)

appear = list(set(appear))
M = len(appear)+1
dic = {v:i for i,v in enumerate(appear)}

for v in appear:
    VW[v] = list(map(int, lines[v].split()))

def dpinit(ps, val=0):
    res = [val for i in [0]*ps[-1]]
    for i in ps[:-1][::-1]:
        res = [res[:] for k in [0]*i]
    return res

maxL = max(Ls)
dp = dpinit((M+1,maxL+2),0)
ans = []

visited = [False] * (M+1)
visited[0] = True
for v,L in vL:
    orgv = v
    seq = []
    v *= 2
    while v:
        v //= 2
        seq.append(v)
        rv = dic[v]
        if visited[rv]:
            break
        visited[rv] = True
    seq = seq[::-1]
    for s,ns in zip(seq,seq[1:]):
        V,W = VW[ns]
        s = dic[s]
        ns = dic[ns]
        for i in range(W):
            dp[ns][i] = dp[s][i]
        for i in range(W,maxL+2):
            dp[ns][i] = max(dp[s][i], dp[s][i-W] + V)
    ans.append(dp[dic[orgv]][L])

for a in ans:
    print(a)

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

Solution code:
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())
for _ in range(q):
  v,l=map(int,input().split())
  s=v
  weights=[]
  values=[]
  z=0
  while s>=1:
    z+=1
    weights.append(W[s-1])
    values.append(V[s-1])
    s=s//2

  dp={0:0}
  for i in range(z):
    w=weights.pop()
    val=values.pop()
    dplist=list(dp.keys())
    for c in dplist:
      p=c+w
      v=dp[c]+val
      if  p in dp and dp[p]>v:
        continue
      elif p<=l:
        dp[p]=v

  x=max(dp.values())
  print(x)

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

Solution code:
N = int(input())
M = 10 ** 5 + 1
K = 9
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
            vv = VV[i-a] + V[b]
            VV[i] = vv
            if ww <= maw:
                ma = max(ma, vv)
        print(ma)
    else:
        V = []
        W = []
        # print("i =", i)
        while i >= 1 << K:
            v, w = A[i]
            # print("v, w =", v, w)
            V.append(v)
            W.append(w)
            i //= 2
        ii = i
        if False:
            print("ii =", ii)
            print("maw =", maw)
            print("X[ii] =", X[ii][:256])
            print("V =", V)
            print("W =", W)
        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
            vv = VV[i-a] + V[b]
            # print("i, ww, vv =", i, ww, vv)
            VV[i] = vv
            if ww > maw: continue
            ma = max(ma, X[ii][maw - ww] + vv)
        print(ma)

Submission status: Wrong Answer

Solution code:

def main():
  n = int(input())

  tree = [map(int, input().split()) for i in range(1, n + 1)]
  tree.insert(0, None)

  memo = [None] * (n + 1)
  memo[0] = [[0, 0]]


  def f(i):
    if memo[i]:
      return

    f(i // 2)
    prev = memo[i // 2]
    v, w = tree[i]
    memo[i] = prev + [(vt + v, wt + w) for vt, wt in prev]


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

    f(v)

    print(max([vt for vt, lt in memo[v] if lt < l]))

main()

Submission status: Wrong Answer

Solution code:
N = int(input())
Items = []
for _ in range(N):
    v, w = map(int, input().split())
    Items.append((v, w))
Q = int(input())
Query = [tuple(map(int, input().split()))for _ in range(Q)]

DP = [[] for _ in range(N)]

for i, (value, weight) in enumerate(Items):
    if i == 0:
        DP[i] = [0] * weight + [value]
    else:
        DP[i] = DP[(i+1)//2 - 1].copy() + [DP[(i+1)//2 - 1][-1]] * weight
        for j in range(weight, len(DP[i]))[::-1]:
            DP[i][j] = max(DP[i][j], DP[i][j-weight] + value)

for v, l in Query:
    if l >= len(DP[v-1]):
        print(DP[v-1][-1])
    else:
        print(DP[v-1][l])
print(DP)

Submission status: Wrong Answer

Solution code:
import sys
from copy import deepcopy as copy
import bisect

def main():
    input = sys.stdin.readline
    n = int(input())
    
    dp = [None]*n
    for i in range(n):
        v, w = map(int, input().split())
        if i == 0:
            dp[i] = {w:v, 0:0}
            continue
        sub = copy(dp[(i-1)//2])
        for key, value in dp[(i-1)//2].items():
            if key+w in sub:
                sub[key+w] = max([sub[key+w], value+v])
            else:
                sub[key+w] = value+v
        dp[i] = copy(sub)
    
    for i in range(n):
        sub = copy(dp[i])
        sub2 = []
        for key, value in sub.items():
            sub2.append((key, value))
        sub2.sort()
        dp[i] = copy(sub2)
    
    q = int(input())
    for _ in range(q):
        v, l = map(int, input().split())
        if True:
            lb, rb = 0, len(dp[v-1])
            while rb-lb > 1:
                index = (rb+lb)//2
                if dp[v-1][index][0] <= l:
                    lb = index
                else:
                    rb = index
            if lb == 0 and dp[v-1][1][0] <= l:
                lb = 1
            print(dp[v-1][lb][1])
            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, VW, Q, VL):
    V = [0] + [v for v, w in VW]
    W = [0] + [w for v, w in VW]

    from collections import Counter
    from functools import lru_cache

    L = 10**5
    @lru_cache(maxsize=None)
    def g(u):
        if u == 1:
            memo = Counter()
            memo[0] = 0
            if W[u] < L:
                memo[W[u]] = V[u]
            return memo

        memo = g(u//2)
        nm = Counter()
        for w, v in memo.items():
            if w+W[u] <= L:
                nm[w+W[u]] = max(nm[w+W[u]], v + V[u])
            nm[w] = max(nm[w], v)
        return nm

    def f(u, l):
        m = g(u)
        ans = 0
        for k in sorted(m.keys()):
            if k > l:
                break
            ans = max(ans, m[k])
        return ans

    ans = []
    for v, l in VL:
        ans.append(f(v, l))
    return ans


def main():
    N = read_int()
    VW = [read_int_n() for _ in range(N)]
    Q = read_int()
    VL = [read_int_n() for _ in range(Q)]
    print(*slv(N, VW, Q, VL), sep='\n')

    # from random import randint
    # N = 2**18
    # Q = 10**5
    # VW = [[randint(1, 10**5), randint(1, 100)] for _ in range(N)]
    # VL = [[i, 10**5] for i in range(1, Q+1)]
    # # print(N)
    # print(*slv(N, VW, Q, VL), sep='\n')



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
stones = [list(map(int,input().split())) for i in range(N)]
DP = [{0:0} for i in range(N)]
DP[0][stones[0][1]] = stones[0][0]
maxL = 10**5
queue = [{} for i in range(N)]
ans_index = []

Q = int(input())
for i in range(Q):
    V,L = map(int,input().split())
    queue[V-1][L] = 1
    ans_index.append([V-1,L])

for i in range(1,N):
    V,W = stones[i]
    par = (i-1)//2
    for w,v in DP[par].items():
        if w in DP[i]:
            DP[i][w] = max(v,DP[i][w])
        else:
            DP[i][w] = DP[par][w]
        if w+W > maxL:
            continue
        if w+W in DP[i]:
            DP[i][w+W] = max(v+V,DP[i][w+W])
        else:
            DP[i][w+W] = v+V

print(0)

Submission status: Wrong Answer

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

n = int(input())

dg = 10**10

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:
        pp = [(0,0)]
        while now >= 2**9:
            tank = []
            for ww,vv in pp:
                if ww+w[now] <= L:
                    tank.append((ww+w[now],vv+v[now]))
            for e in tank:
                pp.append(e)
            now = now//2
        
        res = 0

        for ww,vv in pp:
            L -= ww
            if a[now][0][0] > L:
                continue
            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
                res = max(res,a[now][ok][1] + vv)

            L += ww
        print(res)

Submission status: Wrong Answer

Solution code:
import math
N = int(input())
from collections import defaultdict
items = defaultdict(lambda: [] * 2)
C = defaultdict(lambda: defaultdict(int))
query = list()


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

max_q_w = 0
max_v = 0
Q = int(input())
for i in range(Q):
  v, l = map(int,input().split())
  query.append([v,l])
  max_q_w = max(max_q_w, l)
  max_v = max(max_v, v)


max_w = min(max_w, 10**5, max_q_w)


for i in range(1, max_v+1):
  oya = math.floor(i/2)
  for w in range(1, max_w+1):
    pass
for v, l in query:
  if l > max_w:
    l = max_w
  print(C[v][l])