ABC138 D - Ki

• https://atcoder.jp/contests/abc138/tasks/abc138_d

概要

• $1~N$までのN頂点を持ち, 頂点$1$を根とする根付き木がある。
• $i$番目の辺($1 \leq i \leq N-1$)は頂点$a_i$と頂点$b_i$を結ぶ
• 各頂点にはカウンタがあり, 初期値は$0$である。
• 各頂点に対して以下の操作が$Q$回行われた時, 最終的な各頂点のカウンタの値を求めよ
  • 頂点$p_j$を根とする部分木に含まれる全ての頂点のカウンタの値に$x_j$を足す

思考

• 愚直解は$O(NQ)$になるのは明白
  • Q頂点の入力に対して毎回dfsする
  • Q頂点の入力($O(N)$)に対してdfs($O(N)$)なので, $O(NQ)$
• それでもとりあえず愚直に書く
• 毎回dfsしている部分はどの頂点に関しても, 根から葉への1方向にしか伝播していない
• 単方向ということは最後にまとめて根からdfsすればOK

解法

• $n-1$本の無向辺を追加して, 更に$q$個の重み(カウンタ値)を保存する
• 頂点$1$からdfsをしながら, カウンタ値を加算と重みの更新を行う
  • dfsをするときに1度通った頂点を使わないように, 通ったか否かをbool値で保持しておくこと
• 最後にN頂点のカウンタ値を出力する

提出

• https://atcoder.jp/contests/abc138/submissions/7317015