D - Maximum Sum of Minimum
- 考えたこと
- 小さい数はなるべく位数の小さい頂点に置きたい
- 小さい数はなるべく小さい数のそばに置きたい
- 証明できればいい
- 木だから位数1の点が沢山ある
- 最小の数xを位数1の点に置くと、1本の辺がxになる
- 0本の辺をxにする方法は存在しない
- だから位数1の点に置くのが最良
- ソートして小さい順に置いていけばよい
- 公式解説
- だいぶ違う話をしてるな
- 大きい方から固めて置いていくメソッド
- 大きい数の集まりが連結であることを保ちながら大きい方から置いていくので、小さい数を端から置いていく僕の方法と結果は同じだと思う
- 原理としては飛地をつくらない
- 僕の方は端から埋める
- 辺を全部チェックしてO(N^2)でも間に合うって書いてあるけど、深さ優先探索でO(N)でしょう
- 位数1の点から埋めていく僕の方法は深さ優先探索の帰り掛け順