木のはなし

競プロで題材にされがちな「木」についてメモしておきます。

木の性質

• 閉路のない連結グラフ
• 
• DAG

  木の用語

  木の直径

• もっとも遠い頂点間距離
• 任意の頂点を一つ選び、そこからもっとも遠い頂点を見つける。その頂点からまたもっとも遠い頂点を見つけると、その間の距離が直径である。
• a-b間が直径だとすると、任意の頂点pについてpからもっとも遠い頂点はaかb

  重心

  最小全域木

• クラスカル法
• プリム法
• 最小全域木に辺を一個付け加えると最短閉路ができる

  木に対するアルゴリズム

• LCA
• Euler Tour
• 全方位木DP
• 二乗の木DP
• HL分解

  一般のグラフにおけるテクニック

  一般のグラフに関する問題でも、（最小）全域木について考えることで見通しが立ちやすくなる問題がある。