ABC187 E - Through Path (500)
全てのクエリを愚直に実行すると$ O(NQ)になって間に合わない
辺毎にいくつ加減するかをクエリ毎に溜めて最後にまとめて実行したい
このままだとクエリの伝搬方向があって面倒
適当に1番の頂点を根として木を見る
クエリを溜めて、それは下方向にのみ伝搬させるようにする
クエリの伝搬を除外する方向によって場合分けする
除外するのが親方向の場合、出発点の頂点で溜める
それ以外の場合、全ての点にその値を足し、除外される子に変動数に-1をかけて溜める
全ての点に足すのは、ここで足した値の合計値を持っておいて、最後の出力時に実際にそれぞれの点に足す
最後に溜めた変動数を子に伝搬させていく
出力時には伝搬してきた変動数に全体に足した値を加えて出力する
クエリの処理と値の変更を分けたので$ O(N+Q)になって間に合う