# ABC138 D - Ki

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

# 概要

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

# 思考

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

# 解法

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

# 提出

  • https://atcoder.jp/contests/abc138/submissions/7317015
Last Updated: 2019-9-2 23:10:44