DOJ logoDOJ
题目
最近添加的题目收藏的题目Workbooks
分类DLC比赛小组团队讨论区
排名
解题数量排行榜连续解题排名DOJ Power 排行榜
评测状态
征题登录注册
DOJ logoDOJ

支持 OI 子任务计分、Elo 等级分和 Discord 账号绑定的社区在线评测系统。

题目
题目列表分类
社区
比赛排名讨论区公告举办外部比赛指南
账号
登录注册评测状态
政策
服务条款DLC 使用规则隐私政策API 文档语言运行环境比赛排名奖励评级与表现
© 2026 DOJ
保留所有权利
题解

两棵树

返回题目

题解

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

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

a−u−v−b.a-u-v-b.a−u−v−b.

只考虑这四个顶点时,令 T2T_2T2​ 为路径

v−a−b−u.v-a-b-u.v−a−b−u.

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

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

当前路径始终至少有三条边。与一个顶点 ppp 相接的路径边至多有两条,因此所需的 (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​ 中, 是叶子,因此 ,且 在操作前的 中连通。在 中删去 并恢复 后, 在操作前的树中也连通。由于操作前两棵树具有良好关系, 只能是单个顶点或整个 。若 ,则 是加入 后的全部顶点,不属于禁止的集合。若 ,则 。但 的选择保证它不与 相接,因此 在新的 中不连通,矛盾。

所以,当且仅当 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​
ppp
(y,z)(y,z)(y,z)
(y,z)(y,z)(y,z)
(y,x)(y,x)(y,x)
(x,z)(x,z)(x,z)
xxx
T2T_2T2​
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
xxx
∣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)