DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Two Trees

Back to problem

Editorial

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

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

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

in T1T_1T1​.

On these four vertices, let T2T_2T2​ be the path

v−a−b−u.v-a-b-u.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 222 or 333.

Treat the four vertices as a connected root set and add every other vertex in increasing distance from this set. Let xxx be a new vertex, and let ppp be its parent in T1T_1T1​ among the vertices already added. The current T2T_2T 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 ppp, so such an edge (y,z)(y,z)(y,z) always exists.

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

If x∉Sx\notin Sx∈/S, restoring the deleted edge (y,z)(y,z)(y,z) cannot destroy connectivity in T2T_2T2. 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∈Sx\in Sx∈S, let R=S∖{x}R=S\setminus\{x\}R=S∖{x}. Since xxx is a leaf of T1T_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 T1T_1T1​ is not a star. Using a linked list for the path T2T_2T2​, the construction runs in O(N)O(N)O(N) time. Over all test cases, the time complexity is and the memory usage is .

Solution written by GPT5.6

uu
u
vvv
bbb
vvv
uuu
2
​
(y,z)(y,z)(y,z)
ppp
(y,z)(y,z)(y,z)
(y,x)(y,x)(y,x)
(x,z)(x,z)(x,z)
xxx
​
SSS
S=WS=WS=W
xxx
T2T_2T2​
(y,z)(y,z)(y,z)
WWW
T
1​
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)