トピック
木の直径
解法
全方位木DP
をやる
BFS を2回する
ある点から最も遠い点から最も遠い点までのパスの長さが直径
参考:
高難易度木問題を解くテクニック集 - Speaker Deck
直径の見方が書いてある。
木の半径(
根を選んだときの木の高さの最小値
)
⌈ 直径/2 ⌉ になる
木の重心
tbw
木の最大安定集合
tbw
実装上の注意
木のparent を持つ配列を作る場合、根の扱いには注意
根のparentを自分自身とする場合、子のリストを作るときに根の子に根を入れないようにする。
メモ
木上の2点間の経路は1通りしかない。