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:
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())
    print(half[0][0])
    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
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+1),):
    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 > max_l:
                    break
            if w_sum > max_l:
                continue
            ret[w_sum] = max(ret[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: 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())
    print(knapsack(vv, l, W, V))

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
Vmax*=20

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)
    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())
V = [0] * N
W = [0] * N
for n in range(N):
  V[n], W[n] = [int(x) for x in input().split(' ')]
Q = int(input())
X = [0] * Q
L = [0] * Q
for q in range(Q):
  X[q], L[q] = [int(x) for x in input().split(' ')]

  
DP = [None] * N  # max value when weight total is equal or less than index
M = 10 ** 5 + 5
def dp(x):
  if DP[x] is not None:
    return DP[x]
  if x == 0:
    prev = [(0, 0)]
  else:
    prev = dp((x+1)//2-1)
  # print(x, prev)
  tmp = []
  W_todo = True
  for w, v in prev:
    tmp.append((w, v))
    tmp.append((w + W[x], v + V[x]))
  tmp = sorted(tmp, key=lambda p: (p[0], -p[1]))
  DP[x] = []
  current_v = -1
  for w, v in tmp:
    if v > current_v:
      DP[x].append((w, v))
      current_v = v
    if w > 10 ** 5:
      break
  return DP[x]

def solve(x, l):
  tmp = dp(x-1)
  for w, v in tmp:
    if w > l:
      break
  return v

for x, l in zip(X, L):
  print(solve(x, l))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
import numpy as np

def main():
    n = int(input())
    l = [list(map(int,input().split())) for i in range(n)]
    dic = {}
    q = int(input())
    Q = []
    lm = 0
    for i in range(q):
        a,b = map(int,input().split())
        lm = max(b,lm)
        Q.append((a,b))
    d = np.zeros(lm+1,dtype=np.int64)
    if l[0][1] <= lm:
        d[l[0][1]] = l[0][0]
    dic[1] = d
    
    def dfs(x):
        if x in dic:
            return dic[x]
        
        v,w = l[x-1]
        li = dfs(x//2)
        d = np.zeros(lm+1,dtype=np.int64)
        d[w:] = np.maximum(li[w:],li[:-w]+v,out=li[w:])
        dic[x] = d
        return d

    for a,b in Q:
        s = dfs(a)
        print(np.max(s[:b+1]))
if __name__ == "__main__":
    main()

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())
    print(half[0][0])
    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 = 0; r = len(half[s])
                while(r-l>1):
                    now = (l+r)//2
                    if half[s][now][0]>L-noww:
                        r = now
                    else:
                        l = now

                x = nowv+half[s][l][1]
                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:
# coding: utf-8
import sys

stdin = sys.stdin
ns = lambda: stdin.readline().rstrip() # ignore trailing spaces
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))


def main():
    #https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_d
    lim = 100000
    n = ni()
    vs,ws = [0]*n,[0]*n
    for i in range(n):
        v,w = na()
        vs[i] = v
        ws[i] = w
    q = ni()
    for qi in range(q):
        v,l = na()
        v -= 1
        memo = [0] + [100000]*lim
        while v != -1:
            for j in range(lim, -1, -1):
                if j+vs[v] <= lim:
                    memo[j+vs[v]] = min(memo[j+vs[v]], memo[j] + ws[v])
            if v == 0:
                v = -1
            else:
                v = (v+1)//2 -1
        
        for j in range(lim, -1, -1):
            if memo[j] <= l:
                print(j)
                break
    return

if __name__ == '__main__':
    main()

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_v = list()
query_l = list()
weight_l = list()


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

ans = weight_l[0]
for i in range(1, N):
    ans = math.gcd(ans, weight_l[i])

max_q_w = 0
max_v = 0
Q = int(input())
for i in range(Q):
  v, l = map(int,input().split())
  query_v.append(v)
  query_l.append(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(0, max_v+1, ans):
  if i == 0:
    continue
  oya = math.floor(i/2)
  for w in range(1, max_w+1):
    if items[i][1] <= w:
      prev = items[i][0] + C[oya][w-items[i][1]]
      best = C[oya][w]
      if prev > best:
        C[i][w] = prev
      else:
        C[i][w] = best
    else:
      C[i][w] = C[oya][w]
for v, l in zip(query_v, query_l):
  if l > max_w:
    l = max_w
  l = int(l / ans) * ans
  print(C[v][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 i in range(1,N+1):
    v,w = items[i-1]
    p = i//2
    dp.append(copy.copy(dp[p]))
    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:
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*20

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)
    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:
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=[Wmax]*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*20
Wmax=10**5+1

D[0]=[Wmax]*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
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)
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      left = 0
      right = len(knapls[anc])
      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:
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+1),):
    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(ret[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: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    from collections import defaultdict
    
    ansv=[]
    answ=[]
    anss=[]
    ansv.append(0)
    answ.append(0)
    anss.append(0)#それまでのmaxを入れる
    
    v,w=MI()
    ansv.append([0,v])
    answ.append([0,w])
    anss.append([0,w])
    
    for i in range(2,N+1):
        v,w=MI()
        dd = defaultdict(int)
        for j in range(len(answ[i//2])):
            k=answ[i//2][j]
            vv=ansv[i//2][j]
        
            dd[k]=max(dd[k],vv)
            nw=k+w
            if nw<=100000:
                dd[nw]=max(dd[nw],vv+v)
                
        Lv=[]
        Lw=[]
        Ls=[]
                
        for k,vv in dd.items():
            Lv.append(vv)
            Lw.append(k)

        
        Lw,Lv = zip(*sorted(zip(Lw, Lv)))
        
        now=0
        for j in range(len(Lv)):
            now=max(now,Lv[j])
            Ls.append(now)
            
        
        ansv.append(Lv)
        answ.append(Lw)
        anss.append(Ls)
                
    
    import bisect
    Q=I()
    for i in range(Q):
        v,Li=MI()
        temp=0
        #print(answ[v])
        #print(anss[v])
        num=bisect.bisect_right(answ[v],Li)
 


        print(anss[v][num-1])
        
        
        
    
        

main()

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 = [[-1] *(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(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]+1)


        

if __name__ == '__main__':
    main()

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

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)
    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
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)
    for i in range(l):
      vn,wn = ls[i]
      rest = L-wn
      if i == 0:
        left = 0
        right = len(knapls[anc])
      elif wn >= ls[i-1][1]:
        if vn <= ls[i-1][0]:
          continue
        left = 0
      else:
        right = len(knapls[anc])
      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())

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