yukicoder：No.806 木を道に
問題
解法
まず，各頂点の次数を求める．これは，A, B に対して map を使ってもいいし，ただの配列でいい．これで求まった次数のうち，3 以上のものに関して操作をしたい．3 以上のものに関しては 2 まで次数を減らさなくてはいけないので，（次数が 2 以上の頂点の次数）- 2 を足し合わせたものを答えにすればよい．そうすれば，必ず次数が 1 である頂点を 2 つと，次数が 2 である頂点を N - 2 こ作ることが出来る．O(N)．
解答
まず，各頂点の次数を求める．これは，A, B に対して map を使ってもいいし，ただの配列でいい．これで求まった次数のうち，3 以上のものに関して操作をしたい．3 以上のものに関しては 2 まで次数を減らさなくてはいけないので，（次数が 2 以上の頂点の次数）- 2 を足し合わせたものを答えにすればよい．そうすれば，必ず次数が 1 である頂点を 2 つと，次数が 2 である頂点を N - 2 こ作ることが出来る．O(N)．