题目大意

给定一棵 $n$ 个节点的树，要求为每个节点分配一个新的节点编号（不能与原来相同），使得所有节点到新位置的距离之和分别达到最小和最大，并输出对应的分配方案。

最小距离和思路

最小距离和的目标是让每个节点尽可能移动到最近的节点。核心思路是利用树的结构特性：

• 采用贪心策略，在 DFS 过程中优先匹配兄弟节点或父子节点
• 通过交换相邻节点的目标位置，使得每次移动的距离尽可能小（通常为 1 或 2）
• 最终确保所有节点都被匹配且不留在原位置

最大距离和思路

最大距离和的目标是让每个节点尽可能移动到最远的节点：

• 利用树的 DFS 序特性，将节点 $u$ 映射到 DFS 序中相距 $n/2$ 的节点
• 这样能保证每个节点移动的距离接近树的直径级别
• 通过计算子树大小，可以准确统计每条边被经过的次数

算法特点

1. 时间复杂度：$O(n)$，通过一次 DFS 即可完成所有计算
2. 空间复杂度：$O(n)$，存储树结构和辅助数组
3. 关键技巧：DFS 序的巧妙运用、贪心匹配策略、子树大小统计

该解法充分利用了树的特殊结构，通过简洁高效的算法实现了最优解的构造。