解答：#480139 (C++14) No.806 木を道に - yukicoder
解法：Σ max(deg(v) - 2, 0) が答え。
辺のつなぎ変えは変更前の頂点の次数を1つ減らし、変更後の頂点の次数を1つ増やす。作成したいグラフの次数列は(1, 1, 2, 2, ...)であるため上記の数が操作数の下限である。逆にうまく辺をつなぎ変えることでぴったり操作数で求めるグラフを作成できるため、これが答えとなる。
解答：#480139 (C++14) No.806 木を道に - yukicoder
解法：Σ max(deg(v) - 2, 0) が答え。
辺のつなぎ変えは変更前の頂点の次数を1つ減らし、変更後の頂点の次数を1つ増やす。作成したいグラフの次数列は(1, 1, 2, 2, ...)であるため上記の数が操作数の下限である。逆にうまく辺をつなぎ変えることでぴったり操作数で求めるグラフを作成できるため、これが答えとなる。