Two Trees

Suppose first that $T_1$ is a star. Every vertex except its center is a leaf of $T_1$. Removing a leaf from a tree leaves the remaining vertices connected, so if a good $T_2$ existed, no leaf of $T_1$ could also be a leaf of $T_2$. Every tree has at least two leaves, while only the center of the star is not a leaf of $T_1$. This is impossible.

Now suppose that $T_1$ is not a star. Then there is an edge $(u,v)$ whose two endpoints both have degree at least $2$. Choose a neighbor $a$ of $$ other than , and a neighbor of other than . The four vertices are distinct and form the path

$$a-u-v-b$$

in $T_1$.

On these four vertices, let $T_2$ be the path

$$v-a-b-u.$$

The two trees have no common edge, and their leaf sets are disjoint, so there is no common connected subset of size $2$ or $3$.

Treat the four vertices as a connected root set and add every other vertex in increasing distance from this set. Let $x$ be a new vertex, and let $p$ be its parent in $T_1$ among the vertices already added. The current $T_2$ is always a path. Choose an edge of this path that is not incident to , delete , and add and . Thus we subdivide one edge of the path by .

The current path always has at least three edges. At most two path edges are incident to one vertex $p$, so such an edge $(y,z)$ always exists.

It remains to prove that this operation preserves the good relationship. Let $W$ be the old vertex set, and suppose that after adding $x$ there is a proper subset $S$ connected in both trees.

If $x\notin S$, restoring the deleted edge $(y,z)$ cannot destroy connectivity in $T_2$. Hence would already have been connected in both old trees. The only possible exception is , but after removing from the new , the path is broken at the deleted edge , so is not connected there.

If $x\in S$, let $R=S\setminus\{x\}$. Since $x$ is a leaf of $T_1$, we have , and is connected in the old . In , suppressing and restoring makes connected in the old tree as well. By the old good relationship, is either one vertex or all of . If , then is the whole new vertex set and is not forbidden. If , then , but was chosen not to be incident to , so is not connected in the new . This is a contradiction.

Therefore a solution exists exactly when $T_1$ is not a star. Using a linked list for the path $T_2$, the construction runs in $O(N)$ time. Over all test cases, the time complexity is and the memory usage is .

Solution written by GPT5.6