頂点 \(v\) だけにコマが \(1\) 個置かれており他の頂点にはコマが置かれていない状況から何回の操作ができるか、つまり、頂点 \(v\) のコマ \(1\) 個が操作回数に寄与できる最大数 \(\mathrm{dp}[v]\) を、全頂点 \(v = 1, 2, \ldots, N\) について求めれば、本問題の答えは \(\sum_{v =1}^N \mathrm{dp}[v] \times A_v\) として得られます。 以下、\(\mathrm{dp}[\ast]\) を動的計画法で求める方法を考えます。

ある頂点 \(v\) からコマを取り除いて、集合 \(S\) 内の頂点それぞれにコマを置いたとすると、各頂点 \(u \in S\) に置いたコマに由来する操作がこの後に \(\mathrm{dp}[u]\) 回可能であり、置いたコマ全体に由来して合計 \(\sum_{u \in S} \mathrm{dp}[u]\) 回の操作がこの後に可能です。 よって、操作回数を最大化するには \(\sum_{u \in S} \mathrm{dp}[u]\) が最大になる \(S\) を選べばよく、

\[\mathrm{dp}[v] = 1 + \max_S \sum_{u \in S} \mathrm{dp}[u] \tag{1}\]

です。ここで、\(S\) は \(v\) に隣接するいくつかの頂点からなる（空でも良い）集合であって \(\sum_{u \in S} W_u \lt W_v\) を満たすもの全てをわたります。

\(S\) は \(W_u \lt W_v\) を満たす頂点 \(u\) らしか含み得ないことから、 式 (1) の右辺も \(W_u \lt W_v\) を満たす頂点 \(u\) らのみに依存するため、\(\mathrm{dp}[v]\) の値は \(W_v\) の小さい \(v\) から順次求めていくことができます。

また、ある固定された \(v\) について式 (1) の右辺を求める問題は、

\(v\) に隣接する全頂点 \(u_1, u_2, \ldots, u_{\deg(v)}\) について、\(u_i\) の価値が \(\mathrm{dp}[u_i]\) 、\(u_i\) のコストが \(W_{u_i} \) と定められている時に、選ぶ合計コストが \(W_v\) 未満という制約下で選ぶ合計価値を最大化せよ

というナップザック問題と見ることができ、これは動的計画法によって \(O(\deg(v) \times W_v)\) 時間で解くことができます。

全頂点について上記のナップザック問題を解くことを考えても、

\[\sum_{v = 1}^N \deg(v) W_v \leq W_{\max} \sum_{v = 1}^N \deg(v) = W_{\max} \times 2M\]

です（ただし、\(W_{\max} \coloneqq \max \lbrace W_1, W_2, \ldots, W_N \rbrace\) ）ので、本問題を \(O(N + MW_{\max})\) 時間で解くことができます。