この問題は重心分解と呼ばれるアルゴリズムを題材にした問題です。

定義（重心）：
木に対し、次の条件を満たす頂点 \(v\) を重心という。

• \(v\) を根としたとき、\(v\) の子のどの部分木のサイズも、元の木の \(1/2\) 以下である。

定理（重心の存在）：
どのような木に対しても重心は存在する。

証明：
次のアルゴリズムで求めることができます。

• 木 \(T\) の適当な頂点 \(r\) を根として、各頂点の部分木のサイズを求めておく
• \(v\) を \(r\) で初期化する。
• 以下を繰り返す：
  • \(v\) の子のどの部分木のサイズも \(T\) の \(1/2\) 以下であるかどうか調べる。
    • そうであるとき、 \(v\) が重心であると答え、アルゴリズムを終了する。
    • そうでないとき、\(v\) の子のうち、部分木のサイズが最大のものを \(v'\) とする。\(v\) を \(v'\) に置き換える。

このアルゴリズムの正当性を確かめます。繰り返しにより \(v\) の深さが大きくなること、葉は停止条件を満たすことからこのアルゴリズムは必ず停止します。このアルゴリズムにより \(u\) が求まったとき、実際に重心の条件を満たしていることを確かめます。1 つ前の繰り返しで停止しなかったことから、\(u\) の (\(r\) を根としたときの) 部分木のサイズは \(T\) の \(1/2\) より大きいので、\(T\) から \(u\) の部分木を除いた木のサイズは \(T\) の \(1/2\) 未満です。また、繰り返しの終了条件を満たしたことから、\(u\) の (\(r\) を根としたときの) 子のどの部分木のサイズも \(T\) の \(1/2\) 以下です。よって、\(u\) を根としたとき、\(u\) の子のどの部分木のサイズも \(T\) の \(1/2\) 以下であり、\(u\) は重心です。∎

以上を踏まえ、元の問題を考えます。 \(2\) 番目の条件を「葉以外の全ての頂点 \(v\) に対し、\(v\) の子の部分木の大きさは \(v\) の部分木の大きさの \(1/2\) 以下である」と読み替えておきます。

木 \(T\) の重心を \(v\) とし、これを根とします。また、\(T\) から \(v\) を取り除いてできる森の各連結成分を \(S_i\) とします。

このとき、次が成り立ちます。

• \(T\) において、\(x\) - \(y\) パスが \(v\) を通る場合、そのような組に対しては \(1\) 番目の条件は満たされます。そうでない場合、\(x,y\) は同じ \(S_i\) に属します。
  
• \(S_i\) の辺および、\(T\) と \(S_i\) の頂点を結ぶ辺をどのように張り替えても、\(v\) に関して \(2\) 番目の条件を満たします。
  

以上から、各 \(S_i\) について元と同じ問題を独立に解けばよいことがわかりました。頂点数 \(1\) の木は明らかに条件を満たすことから、再帰的に解くことができます。

木の重心を求めることは \(O(頂点数)\) ででき、再帰ごとに木のサイズは \(1/2\) 以下になるため再帰は \(O(\log N)\) 回しか行われず、全体で \(O(N\log N)\) で問題を解くことができます。

なお、\(R\) が \(T\) を重心分解したものであることは、条件を満たすための十分条件ですが必要条件ではありません。出力例1は、重心分解以外の例です。

Bonus: この問題の正誤判定を高速に行うアルゴリズムを考えてください。