srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

オイラーツアー

codeforces 225 div1 C. Propagating tree

問題 問題概要 (1)頂点vにxを加算し、その子に-xを加算し、またその子にxを加算する。 (2)頂点xの値を求める 解法 オイラーツアーで求めた順番で隣あうものは頂点の深さの差が1である。これを利用すれば、プラスマイナスの加算をsegtreeを2つ使って行うこと…