■ トピック

• 根付き木

  • 自然に辺の向きが定まる（根に向かう向き or その逆）

• 木の直径

  • 解法
    • 全方位木DP をやる
    • BFS を2回する
      • ある点から最も遠い点から最も遠い点までのパスの長さが直径
  • 参考: 高難易度木問題を解くテクニック集 - Speaker Deck
    • 直径の見方が書いてある。

• 木の半径（根を選んだときの木の高さの最小値）

  • $\lceil \text{直径}/2 \rceil$ になる

• 木の重心

  • tbw
  • 高難易度木問題を解くテクニック集 - Speaker Deck を見ると良い？
  • 中央値の一般化
  • ABC348 E - Minimize Sum of Distances
  • メモ

  

• 木の最大独立集合

  • 1つ根を決めて根付き木を作り、葉から貪欲に選べばよい
  • 一般のグラフの場合は NP 困難らしい
  • なもりグラフであれば、ちょっと頑張ると O(N) で解ける（閉路の部分が貪欲だとだめなので、DPをすることになる）
    • AIが作ったメモ

• ケイリーの定理

■ 木上の累積和

• 根からの集約: 根からのパスの集約
• 葉からの集約: 部分木の集約値

■ 木の直径

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

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

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

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