この問題の正誤判定方法を考えます。

正確な問題は次の通りです：
\(N\) 頂点の木 \(T\) と \(N\) 頂点の根付き木 \(R\) が与えられます。いずれも頂点には \(1\)～ \(N\) の番号がついています。次の条件をともに満たすか判定してください。

• \(1\leq x< y \leq N\)を満たす全ての整数の組 \((x,y)\) について、\(R\) における \({\rm LCA}(x,y)\) は \(T\) における \(x\) - \(y\) パス上にある
• \(R\) の根以外の全ての頂点 \(v\) について、(\(v\) の部分木のサイズ) \(\times 2 \leq \) (\(v\) の親の部分木のサイズ) を満たす

まず \(2\) 番目の条件を満たすか判定します。これは \(O(N)\) で容易に確かめられます。\(2\) 番目の条件を満たす場合に限り、\(1\) 番目の条件を満たすかどうか判定することにします。

\(1\) 番目の条件を次の通り読み替えるための準備をします。

• \(R\) において、\(x,y\neq v\) かつ \({\rm LCA}(x,y)=v\) である \(\Longleftrightarrow\) \(R\) において、\(x,y\) が \(v\) の子の異なる部分木に属する
• \(T\) において、\(x,y\neq v\) かつ \(v\) が \(x\) - \(y\) パスに属する \(\Longleftrightarrow\) \(T\) において \(v\) を根としたとき、\(x,y\) が \(v\) の子の異なる部分木に属する

このことから、\(1\) 番目の条件が成り立つことを示すには \(R\) の各頂点 \(v\) に対して、\(v\) の異なる子の部分木に含まれる頂点が、\(T\) においてもそうであることを示せば十分です。

これはさらに、\(R\) の \(v\) の各子の部分木について、「各頂点が \(T\) において \(v\) のどの子の部分木に属するか」を求め、これらのなす集合がdisjoint であることを示せば十分です。

\(R\) における \(v\) の部分木の各頂点に対し、「\(T\) において \(v\) のどの子の部分木に属するか」は \(T\) に対する( \(v\) に依存しない)適当な前計算の下で \(O(\log N)\) で判定できます。したがって、\(v\) を固定したとき、\(O(v \text{ の部分木のサイズ }\log N)\) で判定することができます。

全体の計算量は \(\sum_v O(v \text{ の部分木のサイズ }\log N)\) であり、\(2\) 番目の条件を満たしているような \(R\) に対しては \(O(N(\log N)^2)\)となります。