考虑这样连边能得到什么。对于原树上某个点 u，它的所有邻边 (u, v) 之间会两两连边，于是就得到了一个新图中的大小为 deg _ u 的完全子图。原树上每条边 (u, v) 都有两个端点 u 和 v，说明在新图中它只会同时出现在 u 和 v 的完全子图，并且两部分仅能通过 (u, v) 这个点相连。有点仙人掌。
考虑这样遍历能得到什么。是一个 dfs，就是能走多远走多远的那种，如果通过 (u, v) 从 u 的完全子图走到 v 的完全子图，会先把后面 v 子树内所有边都遍历完再回溯回来，再走另一个 (u, w)，然后生成树连一条 (u, v) - (u, w) 的边。很难不发现这会在 u 的完全子图中得到一个 长为 deg _ u 的短链。最终的生成树是 n 个这样的短链拼起来的。
再考虑从 (u, v) 开始遍历的话，先进入 v 的完全子图，那很明显 (u, v) 会是短链的一个链头。如果另一个链头是 (v, w) 的话，从 (v, w) 进入到 w 的完全子图，同时 (v, w) 成为了 w 短链的链头……反过来 u 这边也一样。于是注意到有且仅有一条极长的链，由一堆完全子图的短链首尾相接构成，而其他完全子图的短链都通过一个链头直接或者间接地挂在这条极长链上。进一步注意到，一条边能生成一棵树，当且仅当这颗树存在这样的极长链，并且这条边在极长链上。(否则无论如何，生成出来的树的极长链都不是这条)。