两棵树

先考虑 $T_1$ 是星形树的情况。除中心以外的所有顶点都是 $T_1$ 的叶子。删去树中的一个叶子后，其余顶点仍然连通。因此，若存在与 $T_1$ 具有良好关系的 $T_2$，则 $T_1$ 的任意叶子都不能同时是 $T_2$ 的叶子。然而，任意一棵树都至少有两个叶子，而星形树 $T_1$ 中只有中心不是叶子，所以这是不可能的。

下面考虑 $T_1$ 不是星形树的情况。此时一定存在一条边 $(u,v)$，其两个端点的度数都至少为 $2$。从 $u$ 的邻点中任选一个不同于 $v$ 的顶点 ，从 的邻点中任选一个不同于 的顶点 。四个顶点 两两不同，并且在 中形成路径

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

只考虑这四个顶点时，令 $T_2$ 为路径

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

两棵树没有公共边，并且它们的叶子集合互不相交，因此不存在大小为 $2$ 或 $3$、在两棵树中都连通的顶点集合。

将这四个顶点看作一个连通的根集合，按照到该集合的距离从小到大加入其余顶点。设新加入的顶点为 $x$，它在 $T_1$ 中、已经加入的顶点中的父亲为 $p$。当前的 $T_2$ 始终是一条路径。从这条路径中选择一条不与 相接的边 ，删除 ，并加入 与 。也就是说，用 将 的一条边细分。

当前路径始终至少有三条边。与一个顶点 $p$ 相接的路径边至多有两条，因此所需的 $(y,z)$ 一定存在。

下面证明这个操作保持良好关系。设操作前的顶点集合为 $W$，并假设加入 $x$ 后存在一个真子集 $S$，它在两棵树中都连通。

若 $x\notin S$，在 $T_2$ 中恢复边 $(y,z)$ 不会破坏 的连通性。因此，操作前 就已经在两棵树中都连通。唯一可能的例外是 ，但从新的 中删去 后，路径会在被删除的边 处断开，所以 并不连通。

若 $x\in S$，令 $R=S\setminus\{x\}$。在当前的 $T_1$ 中， 是叶子，因此 ，且 在操作前的 中连通。在 中删去 并恢复 后， 在操作前的树中也连通。由于操作前两棵树具有良好关系， 只能是单个顶点或整个 。若 ，则 是加入 后的全部顶点，不属于禁止的集合。若 ，则 。但 的选择保证它不与 相接，因此 在新的 中不连通，矛盾。

所以，当且仅当 $T_1$ 是星形树时不存在答案。使用链表维护 $T_2$ 的路径即可在 $O(N)$ 时间内完成构造。所有测试用例的总时间复杂度为 $$，空间复杂度为 。

Solution written by GPT5.6