たのしく木グラフ : 競プロ典型 90 問 003 - Longest Circular Road（★4）
問題
読み替え
グラフを扱う問題です．
N個の頂点とN-1本の辺が与えられます．これで作られるグラフは連結*1です．
ある頂点uと頂点vの間に辺を1本張ることを考える時，サイクル*2ができる場合があります．このとき．サイクルの長さの最大値を求めてください．
解説
頂点がN個で辺がN-1本の連結グラフを考えると，そのグラフにサイクルが含まれることはありません．これは数学的帰納法で示すことができます．このグラフは木というグラフクラスに含まれます．木の特徴は次のとおりです．
- ある頂点uからある頂点vまでの経路を考える時，それを満たす経路は1つしか存在しない．
- ある頂点uとある頂点vの間に辺を張ることを考えると，サイクルができる．そのサイクルの長さはuからvへの経路の長さ+1である．
これを利用して問題を解きます．
ある頂点から最も経路の長さが長い頂点とその長さを求めるのはBFSを利用することでO(N)できます．BFSは幅優先探索で与えられた頂点と隣接する(辺を持つ))頂点を連続的に見ることで条件を満たす頂点*3を探す手法です．
図を用いて説明します．
上の図では始点として赤の頂点を考えます．それを距離0の頂点とし，隣接する頂点を見ていきます．今回の場合だと左上の頂点と真ん中の頂点が対象です．これらについて距離1の頂点とします．同様に距離1の頂点と隣接する頂点それぞれについて距離2の頂点とします．ただし，既に始点からの距離がわかっている頂点については更新しないこととします．これを全ての頂点について始点からの距離がわかる状態になるまで繰り返します．
最後に最も始点からの距離が長い頂点の1つを選び，返します．
BFSを全ての始点について行うことで解を得ることを考えたいのですが，O(N2)となり，制約としてN<100000であるため，N=100000の場合などには2秒以内に計算を終えることができません．
しかし次のようにBFSを2回だけ行うことで解を得ることができます．
- ある頂点vを選びBFSを用いてvを始点とする最も距離の長い頂点sを得る．
- BFSを用いて頂点sを始点とする最も距離の長い頂点tを得て，その距離+1を出力する
これは木の直径を求めるアルゴリズムで，木の最も距離の長い頂点の組と距離を得ることができるアルゴリズムとして知られています．これはN=100000の場合でも問題なく2秒以内に動作させることができます．最も距離が得られたため，サイクルの長さはその距離+1となります．
BFSの実装については先駆者が多くいますのでそちらを参考にしてください．
