木の直径
直径: 木の最短路のうち、最も長いもののこと（最長単純パスとも言う）
半径: 直径/2
中心: 他の点への最短路の最大値が最小になる点
重みなし木の直径
直径を求めるアルゴリズム (Double-Sweep) $ O(N)
1. 適当な点$ uからBFSをして$ uからの最遠点$ vを求める（$ vは葉になる）
2. $ vからBFSをして$ vからの最遠点$ wを求める（$ wは葉になる）
3. $ vと$ wの最短距離が直径
このアルゴリズムで最初に適当な点$ uからの最遠点$ vを求めるのは、葉を求めるため（最遠点は必ず葉になる）
直径のパス
直径のパスは、以下のような性質がある
端点は木の葉
中心を通る
直径が偶数なら中心は1つ
直径が奇数なら中心は2つ
中心を求めるアルゴリズム $ O(N)
直径が偶数の場合
$ vからの距離も$ wからの距離も直径/2と等しくなる点
直径が奇数の場合
$ vからの距離がfloor(直径/2)で、$ wからの距離がceil(直径/2)となる点
$ vからの距離がceil(直径/2)で、$ wからの距離がfloor(直径/2)となる点
直径のパスの数え上げ
直径のパスは必ず中心を通ることを使う
中心が2つのとき
それぞれの中心から最も遠い葉の個数を掛ける
https://gyazo.com/d90708d4728415b32822e62023efe84c
図の例では、$ 3 \times 2 = 6本
中心が1つのとき
中心から生えているそれぞれの部分木について、中心からの距離が半径のものを数える
そこから2つの部分木を選んで、距離が半径な葉の個数を掛ける
https://gyazo.com/441c8861045f374e9d852da5e4ba98b1
図の例では、$ 1 \times 2 + 1 \times 3 + 2 \times 3 = 11本
累積和を取ったりしてうまくやると$ O(N)で求まりそう
テクニック
数え上げしたいだけなら、すべての辺の間に頂点を挿入すると、直径が2倍になり、中心は1つになる（直径のパスの本数は変わらない）
このようにすることで、中心が1つのときだけを考えればよくなる
https://gyazo.com/47a5c82be00020dc3ca8b38fce822ad4
重みあり木の直径
Double-Sweep
重みあり木でも有効
わかりません
木DPをすると$ O(N)で求めるらしい
参考