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