頂点 \(u\) と \(v\) に対し \(\mathrm{LCA}(u, v)\) で二つの頂点の最近共通祖先を表すとします。

突然ですが、 \(S = \lbrace \mathrm{LCA}(V_i, V_j) \mid 1 \leq i, j \leq M \rbrace\) として頂点集合 \(S\) を定めます。

後のために、先に \(S\) を \(\Theta(N + M)\) 時間で計算する方法を解説します。 \(c_i\) を、頂点 \(i\) を根とする部分木に最初の時点で置かれている駒の数と定義します。すると、 \(i \in S\) \(\iff\) (異なる二つの頂点 \(i\) の子 \(x, y\) が存在して \(c_x > 0, c_y > 0\) またはある \(j\) が存在して \(V_j = i\)) が成立します。よって、実際に葉の方から \(c_i\) を求めていくことで \(S\) が計算できました。

\(S\) について以下の事実が成立します。

• 任意の \(u, v\in S\) に対し、 \(\mathrm{LCA}(u, v) \in S\)

証明: \(u = \mathrm{LCA}(u, v)\) または \(v = \mathrm{LCA}(u, v)\) の場合は明らかに成り立つので、 \(u \neq \mathrm{LCA}(u, v), v \neq \mathrm{LCA}(u, v)\) とします。ここで、 \(c_u > 0, c_v > 0\) であることから、\(\mathrm{LCA}(u, v)\) にはある二つの子 \(x, y\) が存在して、 \(c_x > 0, c_y > 0\) です。よって、先ほど解説した \(S\) の計算方法より、 \(\mathrm{LCA}(u, v) \in S\) です。

これより、駒がいる頂点は常に \(S\) に含まれることになります。

\(\lbrace t_i \rbrace = (t_1, t_2, \ldots, t_M)\) として考えられるものはどのようなものなのかを考えましょう。

まず明らかに、任意の \(i\) について 頂点 \(t_i\) は頂点 \(V_i\) の先祖である必要があります。また、任意の \(i\) について \(t_i \in S\) である必要があります。

逆に、この二つの条件を満たすとき、最終的に \(\lbrace t_i \rbrace = (t_1, t_2, \ldots, t_M)\) となるようにコマを動かすことが可能です。具体的には、 \(t_i\) が深い \(i\) から順に駒 \(p\) として選んで動かせば良いです。

以上より、この問題は \(\Theta(N+M)\) 時間で解くことができました。