二つの木

まず、$T_1$ がスターである場合を考えます。中心以外のすべての頂点は $T_1$ の葉です。木から葉を 1 個取り除いても残りの頂点は連結なので、良い関係にある $T_2$ が存在するなら、$T_1$ の葉が $T_2$ の葉でもあることはありません。しかし、どの木にも葉は少なくとも 2 個あります。一方、スター $T_1$ で葉でない頂点は中心の 1 個だけなので、これは不可能です。

次に、$T_1$ がスターでない場合を考えます。このとき、両端点の次数がともに $2$ 以上である辺 $(u,v)$ が存在します。$u$ の $v$ 以外の隣接頂点を一つ 、 の 以外の隣接頂点を一つ とします。 は相異なる頂点であり、 上で

$$a-u-v-b$$

というパスをなします。

この 4 頂点だけを考え、$T_2$ を

$$v-a-b-u$$

というパスにします。二つの木は共通の辺を持たず、葉の集合も互いに素です。したがって、大きさが $2$ または $3$ の頂点集合で、両方の木において連結なものは存在しません。

残りの頂点は、この 4 頂点からなる連結部分を根の集合とみなし、そこからの距離が小さい順に追加します。新しく追加する頂点を $x$、すでに追加された頂点のうち $T_1$ における $x$ の親を $p$ とします。現在の $T_2$ は常に一本のパスです。このパスから に接続していない辺 を一つ選び、 を削除して を追加します。つまり、 の辺を で分割します。

現在のパスには常に少なくとも 3 本の辺があります。一つの頂点 $p$ に接続するパスの辺は高々 2 本なので、条件を満たす $(y,z)$ は必ず存在します。

この操作が良い関係を保つことを示します。操作前の頂点集合を $W$ とし、$x$ を追加した後に、両方の木で連結な真部分集合 $S$ が存在すると仮定します。

$x\notin S$ の場合、$T_2$ に辺 $(y,z)$ を戻しても の連結性は失われません。よって、操作前にも は両方の木で連結だったことになります。唯一の例外候補は ですが、新しい から を除くと、削除した辺 の位置でパスが切れるため、 は連結ではありません。

$x\in S$ の場合、$R=S\setminus\{x\}$ とします。現在の $T_1$ では は葉なので であり、 は操作前の で連結です。また、 では を取り除いて を戻すと、 は操作前の木で連結になります。操作前の二つの木は良い関係にあるため、 は 1 頂点だけ、または 全体のどちらかです。 なら は新しい頂点集合全体なので禁止される集合ではありません。 なら ですが、 は に接続しないように選んだため、 は新しい で連結ではありません。矛盾です。

したがって、答えが存在しないのは $T_1$ がスターである場合に限ります。$T_2$ のパスを連結リストで管理すれば、構成は $O(N)$ 時間で行えます。全テストケースでは時間計算量は 、空間計算量は です。

Solution written by GPT5.6