CF1867F Most Different Tree

给定一棵有 $n$ 个顶点、以顶点 $1$ 为根的树，记为 $G$。记 $P(G)$ 为树 $G$ 中所有顶点的子树组成的多重集。你需要构造一棵同样大小、以顶点 $1$ 为根的树 $G'$，使得 $P(G')$ 中与 $P(G)$ 中任一子树同构的子树数量最少。 一个顶点 $v$ 的子树是指包含所有从树的根到自身路径上经过 $v$ 的顶点，以及这些顶点之间所有边的图。 两棵有根树被认为是同构的，当且仅当可以重新标号其中一棵树的顶点，使其与另一棵树完全相同，并且第一棵树的根被标号为第二棵树的根。

第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示树 $G$ 的顶点数。接下来的 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a,b \leq n$），表示在树中顶点 $a$ 和顶点 $b$ 之间有一条边。

输出 $n-1$ 行，每行包含两个整数 $a$ 和 $b$（$1 \leq a,b \leq n$），表示树 $G'$ 的一条边。如果有多组最优解，输出任意一组均可。

由 ChatGPT 4.1 翻译