1/27 PKU

3417 Network

木構造にM本の辺を加えたグラフから2本の辺を取り去って、グラフを非連結にしたい。取り去る辺は、1本は最初からある木の辺で、もう1本は加えられた辺でないといけない。何通りの方法があるか。

取り去る辺のうち、木の中の辺の方に注目すると、その辺を「またぐ」新しい辺が存在しないときはどれを取り去ってもよく、１本だけ存在するときはそれを取り去ると被連結にできる。２本以上のときは不可能。「またぐ辺」は、例えばa--bの辺が追加されたときは、木のa--bの経路上の辺に1を加算するなどして、各辺について計算できる。