データ構造/木

ABC070 D: Transit Tree Path

D - Transit Tree Path 解き方 aからKへの距離とKからbへの距離の和を出力する Kから各頂点への最短距離は、木なので、DFSすればO(n)で求まる。 ハマったところ 0-indexと1-index混ぜてた 読み込み時に変えておくべきという話はありそう 最初全頂点から全頂…

ARC 076 D: Built?

http://arc076.contest.atcoder.jp/tasks/arc076_b 解き方 コストの定義を使って,辺の数をO(N)に削減 最小全域木をクラスカルなりプリムなりで求める プリムの場合はpriority_queueを使った実装じゃないと多分間に合わない ハマった所 プリム,クラスカルの…