DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

二つの木

問題に戻る

解説

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

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

a−u−v−ba-u-v-ba−u−v−b

というパスをなします。

この 4 頂点だけを考え、T2T_2T2​ を

v−a−b−uv-a-b-uv−a−b−u

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

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

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

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

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

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

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

Solution written by GPT5.6

v
aaa
vvv
uuu
bbb
a,u,v,ba,u,v,ba,u,v,b
T1T_1T1​
2​
ppp
(y,z)(y,z)(y,z)
(y,z)(y,z)(y,z)
(y,x),(x,z)(y,x),(x,z)(y,x),(x,z)
T2T_2T2​
xxx
z
)
SSS
SSS
S=WS=WS=W
T2T_2T2​
xxx
(y,z)(y,z)(y,z)
WWW
​
xxx
p∈Rp\in Rp∈R
RRR
T1T_1T1​
T2T_2T2​
xxx
(y,z)(y,z)(y,z)
RRR
RRR
WWW
R=WR=WR=W
SSS
∣R∣=1|R|=1∣R∣=1
R={p}R=\{p\}R={p}
(y,z)(y,z)(y,z)
ppp
{p,x}\{p,x\}{p,x}
T2T_2T2​
O(∑N)O(\sum N)
O(∑N)
O(N)O(N)O(N)