問題概要
$n$ 頂点の木 $T = ( V, E )$ が与えられる．
$T$ に辺を $1$ 本追加して得られるグラフはちょうど $1$ つの閉路をもつが，そのようなグラフの内，以下の条件をともに満たすものの個数を求めよ：
- 単純グラフである．
- 唯一の閉路に含まれる頂点の次数はすべて $3$ である．
制約
- $3 \leq n \leq 2 \times 10^5$
解法
グラフ $G = ( V, E )$ に辺 $e$ を追加して得られるグラフ $( V, E \cup e )$ を $G \cup e$ と略記することにします．
あるグラフについて条件を真面目にチェックすると $O( n )$ 時間かかることなどから，そのままやるとつらそうに見えます．なので，$2$ 点 $u, v$ について， $T \cup \{ u, v \}$ に関する条件を辺からの視点で言い換えられないか考えます．ひとつめの「グラフが単純であること」は，（「単純」の定義から）$T \cup \{ u, v \}$ がループも多重辺も含まないことであり，$u \neq v$ かつ $\{ u, v \} \not \in E$ と同値です．ふたつめの「閉路に含まれる頂点の次数がすべて $3$」は，辺の追加によって次数が変化するので，閉路に含まれる頂点を $u, v$ とそれ以外について分けて考えます．$u, v$ 以外の頂点の次数は変化しないため，$T$ において次数が $3$ である頂点であり，$u, v$ の次数は辺 $\{ u, v \}$ の追加によって $1$ 増加するため，$T$ において次数 $2$ であった頂点だと言えます．これらをまとめると，辺 $\{ u, v \}$ は，
- $u, v$ は $T$ において次数 $2$
- $T$ における $u$-$v$ 単純パスから端点を除いた部分が $1$ つ以上の次数 $3$ の頂点からなる
とき，$T \cup \{ u, v \}$ は条件を満たします．
$u, v$ の取り方をすべて試すことは（$\Theta( n^2 )$ 通りあることから）できないので更に視点を変えて，$u$-$v$ パスの端点以外の部分に着目します．これらの頂点はすべて次数 $3$ の頂点のみを経由して連結*1なので，ある次数 $3$ の頂点 $w$ に着目すると，そこから（$w$ 自身を含め）次数 $3$ の頂点のみを経由して到達できる次数 $3$ の頂点に隣接する次数 $2$ の頂点 $u, v$ を結ぶ辺 $\{ u, v \}$ が，$T \cup \{ u,v \}$ が条件を満たすものであると言えます．
従って，次数 $3$ の頂点のみからなる塊ごとにそこに隣接する次数 $2$ の頂点を数えることで，追加できる辺の本数が分かります．具体的には，そのような（次数 $2$ の）頂点の個数を $k$ とすれば，そこから相異なる $2$ 点を選ぶ方法の数が feasible な辺の本数であり，これは $\binom k 2 = \frac { k ( k - 1 ) } 2$ と計算できます．
次数 $3$ の頂点の塊およびそこに隣接する頂点は，適当な次数 $3$ の頂点から深さ優先探索 (Depth-First Search; DFS) をすることで発見できて，次数 $3$ の各頂点について訪問済みか否かを管理しておくことで重複して数えてしまうことを防げます．各辺が次数 $3$ の頂点からしか辿られないことに注意すれば，$O( n )$ 時間のアルゴリズムになっていることが分かり，問題に正答できます．
コード
int dfs( const VVI &G, const int u ) { if ( SZ( G[u] ) == 2 ) { return 1; } if ( SZ( G[u] ) != 3 ) { return 0; } static bool visited[ 1 << 18 ]; if ( visited[u] ) { return 0; } visited[u] = true; int res = 0; FOR( v, G[u] ) { res += dfs( G, v ); } return res; } int main() { IN( int, N ); VVI G( N ); REP( N - 1 ) { IN( int, u, v ); --u, --v; G[u].PB( v ); G[v].PB( u ); } LL res = 0; REP( u, N ) { const int r = dfs( G, u ); res += LL( r ) * ( r - 1 ) / 2; } cout << res << endl; return 0; }
