データ構造/木

ARC083 E: Bichrome Tree

E - Bichrome Tree 解き方 ある頂点iの部分木について、黒白それぞれの重みの和を、b_i, w_iとして、それを更新していく 黒白は入れ替えても問題ないので、違う色か同じ色かだけ考えれば良い 頂点iがleafの場合、色はどちらでもよく、重みはx_iになる 頂点i…

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を使った実装じゃないと多分間に合わない ハマった所 プリム,クラスカルの…