ABC138 D - Ki
- https://atcoder.jp/contests/abc138/tasks/abc138_d
概要
- 1NまでのN頂点を持ち, 頂点1を根とする根付き木がある。
- i番目の辺(1≤i≤N−1)は頂点aiと頂点biを結ぶ
- 各頂点にはカウンタがあり, 初期値は0である。
- 各頂点に対して以下の操作がQ回行われた時, 最終的な各頂点のカウンタの値を求めよ
- 頂点pjを根とする部分木に含まれる全ての頂点のカウンタの値にxjを足す
思考
- 愚直解は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