と、思ったけど、O(n) でできるのか。
最初に根となる頂点を一つ選んで、
枝を根から葉の方向に向きをつけておく。
一つ目の再帰では、常に現在見ている部分木の根を v としてとるようにすれば、
ちょん切り方を数える再帰では、各頂点ごとに一回だけ数えて覚えておけば再利用できる。

どちらの再帰も各頂点ごとに一度づつ実行されるので、トータルで O(n)。