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