Tree問題codeforces.com問題概要Tree(重み付きではない)が与えられ、木の各頂点に数字を書き込む。以下のM個のクエリも与えられる。頂点vと、その部分木のうち、vからの距離がd以内に含まれる頂点にxを足す。昔似た方針で解いた記憶がある。リアルタイムimosって感じ。DFSで頂点を見ていく。DFSでは、一個前の頂点で書き込んだ数字を引数として持っておく(sとする)。見た頂点から、d,xなクエリが発行されていたら、sにxを一通り足す。同時に、木の最大の深さ分の配列を用意しておいて、今見ている頂点の深さに、dを足した先にxを足してメモしておく。xを一通り足したら、memoでメモされている分を引く。(そのクエリの範囲外に到達するため)また、今見ている頂点が見終わったら、memoに足した分は無効化されるので、最後に引いて終了しないといけない。writeup月別アーカイブはてなブログをはじめよう!kurenaifさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。