ABC138 D - Ki - 7K4B blog

f:id:tkr987:20200728234724p:plain

https://atcoder.jp/contests/abc138/submissions/15508780

根の値 < 部分木の値に必ずなる⇒累積和

f:id:tkr987:20200729000832p:plain

制約から各クエリを $O(\log N)$ 以下で処理しなければならない。根の値が伝搬されて必ず「根の値 < 部分木の値」になることから累積和になっていることが分かる。DS_NyaaCumulativeSumライブラリを使わずにクエリをmapにしてDFSで辿りながら res[v] = res[r] + q[v] で累積和の処理をした。累積和を使った合計は $O(1)$ で取得、ボトルネックはクエリをmapで取得する $O(\log Q)$ 、全体計算量は $O(N \log Q)$ になる。