Village (Minimum)

Village (Minimum)

边长为1的树上，每一个节点移动到另外一个不同的节点，求最小的总移动距离和。

这是一个比较巧妙的greedy算法，有点难理解，但是写起来非常简单:

  1. DFS顺序遍历所有节点
  2. 对于没有发生过交换的非根节点，和父亲交换，总移动距离+2。
  3. 对于根，和任何一个儿子交换，距离+2.

这个正确的原因如下：

  1. 对于没有和根发生过交换的节点，这样操作的最后结果，就是或者停留在父亲处（移动了1），或者停留在兄弟处（移动了2）。 不存在比这个更近的移动方案了，去其它地方都更远。
  2. 因为每次交换要求有至少一个没有动过，这就保证了这两个节点都不会回到最初的位置。每次这样操作后，在原位的节点数 就减少1或者2. 所以最近最多N次操作（一次DFS），就完成了。
  3. 根的操作增加的是最小值2，所以也是最优的。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n;      // 1e5
vector<int> adj[100005];
int ans;
int moveto[100005];
 
void dfs(int s, int e) {
    for (int u: adj[s]) {
        if (u == e) continue;
        dfs(u, s);
    }
    if (s != 0 && moveto[s] == s) { // non-root nodes that are not moved - swap with parent
        moveto[s] = e;
        moveto[e] = s;
        ans += 2;
    } else if (s == 0 && moveto[0] == 0) {    // if root is not moved - swap with any child
        moveto[0] = *adj[0].begin();
        moveto[*adj[0].begin()] = 0;
        ans += 2;
    }
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n-1; i++) {
        int u,v;
        scanf("%d %d", &u, &v);
        u--,v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 0; i < n; i++) moveto[i] = i;
    dfs(0, -1);
    printf("%d\n", ans);
    for (int i = 0; i < n; i++) {
        printf("%s%d", i ? " " : "", moveto[i]+1);
    }
 
    return 0;
}