木構造 | Notion

トピック

根付き木
- 自然に辺の向きが定まる（根に向かう向き or その逆）
木の直径
- 解法
  - 全方位木DP をやる
  - BFS を2回する
    - ある点から最も遠い点から最も遠い点までのパスの長さが直径
- 参考: 高難易度木問題を解くテクニック集 - Speaker Deck
  - 直径の見方が書いてある。
木の半径（根を選んだときの木の高さの最小値）
- ⌈ 直径/2 ⌉ になる
木の重心
- tbw
- 高難易度木問題を解くテクニック集 - Speaker Deck を見ると良い？
- 中央値の一般化
- ABC348 E - Minimize Sum of Distances
木の最大安定集合
- tbw
ケイリーの定理

木の直径

求め方
- 全方位木DP をやる
- BFS を2回する
テク
- 直径を横に並べて、その直径を根とする根付き木を考える
  - 参考: 高難易度木問題を解くテクニック集 - Speaker Deck
問題
- 木の直径はいくつあるか
  - 参考: 高難易度木問題を解くテクニック集 - Speaker Deck

木の根を任意に選んで良いパターン

どこを根にしてもいいからとりあえず根付き木を考えるとよいことがある。

根付き木を考えることで LCA が考えられたり、木DP ができたりする。