두 트리

$T_1$이 별 모양 트리라고 하자. 중심이 아닌 모든 정점은 $T_1$의 리프이다. 트리에서 리프 하나를 제거하면 남은 정점들은 연결되어 있으므로, 좋은 관계인 $T_2$가 존재한다면 $T_1$의 리프는 $T_2$의 리프가 될 수 없다. 하지만 모든 트리는 리프를 적어도 두 개 가지므로 이는 불가능하다.

이제 $T_1$이 별 모양이 아니라고 하자. 그러면 양 끝점의 차수가 모두 $2$ 이상인 간선 $(u,v)$가 존재한다. $u$의 $v$가 아닌 이웃 하나를 , 의 가 아닌 이웃 하나를 라고 하자. 네 정점 는 서로 다르며, 에서

$$a-u-v-b$$

라는 경로를 이룬다.

이 네 정점만 있을 때 $T_2$를

$$v-a-b-u$$

라는 경로로 잡는다. 두 트리는 공통 간선을 가지지 않고, 두 트리의 리프 집합도 서로 겹치지 않으므로 크기 $2$ 또는 $3$인 공통 연결 부분집합이 없다.

나머지 정점들은 네 정점으로 이루어진 경로를 루트 집합으로 보고, 그 집합과의 거리가 가까운 순서대로 추가한다. 새로 추가하는 정점을 $x$, 이미 추가된 정점 중 $T_1$에서 $x$의 부모를 $p$라고 하자. 현재 $T_2$는 항상 하나의 경로이다. 이 경로에서 를 끝점으로 가지지 않는 간선 를 하나 골라 를 지우고 를 추가한다. 즉, 의 간선 하나를 로 분할한다.

현재 경로에는 항상 간선이 적어도 세 개 있다. 한 정점 $p$에 닿는 경로의 간선은 최대 두 개이므로 필요한 $(y,z)$는 항상 존재한다.

이 연산이 좋은 관계를 보존함을 보이자. 연산 전의 정점 집합을 $W$라 하고, 연산 후 두 트리에서 공통으로 연결된 적절한 부분집합 $S$가 존재한다고 가정한다.

$x\notin S$라면, $T_2$에서 $(y,z)$를 복원해도 의 연결성은 사라지지 않는다. 따라서 연산 전에도 가 두 트리에서 연결되어야 한다. 유일한 예외 후보는 이지만, 연산 후 를 제외하면 의 경로가 에서 끊어지므로 는 연결되어 있지 않다.

$x\in S$라면 $R=S\setminus\{x\}$를 생각한다. $x$는 $T_1$에서 리프이므로 이고 은 연산 전의 에서 연결되어 있다. 에서는 를 없애고 를 복원하면 이 연결된다. 따라서 연산 전에도 은 두 트리에서 연결되어 있다. 연산 전의 좋은 관계 때문에 은 한 정점이거나 전체뿐이다. 이면 가 전체 정점 집합이 되어 조건의 대상이 아니다. 이면 인데, 를 에 닿지 않게 골랐으므로 는 에서 연결되어 있지 않다. 모순이다.

따라서 $T_1$이 별 모양일 때만 답이 존재하지 않는다. 구성은 연결 리스트로 $T_2$의 경로를 관리하면 전체 $O(N)$ 시간에 수행할 수 있다. 모든 테스트 케이스에 대해서도 시간 복잡도는 이고, 메모리 사용량은 이다.

Solution written by GPT5.6