CF1387B1 Village (Minimum) 题解

题目链接：CF1387B1 Village (Minimum)

题意：

村里 \(n\) 个房子构成了一个 \(n\) 点 \(n-1\) 条边的树结构（下标从 \(1\) 开始），每条边长度均为 \(1\)。一开始每个房子里分别有一个村民。

现在所有村民都需要搬家（改变自己所在的点），搬家后依然需要满足每个房子里有且只有一个村民。也就是说，如果原本位于点 \(i\) 的村民搬到了点 \(v_i\)，那么应当满足：

• 对于任意点 \(i\)，有 \(i \neq v_i\)。

• 对于任意两个不同的点 \(i\) 与 \(j\)，有 \(v_i \neq v_j\)。

村民 \(i\) 搬家的花费是点 \(i\) 到点 \(v_i\) 的树上距离（即树上二点间相隔的边数），总花费为所有村民花费之和。求总花费的最小值及其方案。

输入格式：

第一行一个正整数 \(n\)，表示树的点数。

接下来 \(n-1\) 行每行二整数 \(a\) 和 \(b\)，表示树上有一条连接 \(a\) 和 \(b\)，长度为 \(1\) 的边。

输出格式：

第一行一个整数，表示总花费的最小值。

第二行 \(n\) 个整数 \(v_1 \dots v_n\)，表示搬家的方案：如果原本位于点 \(i\) 的村民搬到了点 \(v_i\)。

输出任意一组合法方案即可。

数据范围：

\(2 \leq n \leq 10^5,~1 \leq a,b \leq n\) 。

首先根据贪心的思想，不难发现任意一个点只会和自己相邻的或者隔一个的交换。

这些点都在链上还是比较好处理的，问题如果这个结点有一堆儿子就很麻烦。

考虑 \(\mathtt{dfs}\) 一遍，然后钦定每个结点与第一个遍历的子结点互换。

接着不是还有一堆儿子没换么。不妨记 \(p_u\) 表示 \(u\) 交换的结点是谁。

我们对于每个没有 \(p_u\) 的结点 \(u\) 和它第一个儿子 \(v\) ，做 \[ \begin{array}{} 1.\ &p_u \gets p_v \\[6pt]2.\ & p_v \gets u \end{array} \] 思路还是蛮 6 的。啥时候也能秒了就好了

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))

int n,m,res,pos=1,head[N],p[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int fa)
{
    for(int i=head[u]; i; i=e[i].next)
    {
        int v = e[i].v; if(v == fa) continue;
        dfs(v,u); if(!p[u] && !p[v]) { tie(p[u], p[v]) = tie(v,u); }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<n; i++)
    { cin >> u >> v; addEdge(u,v); addEdge(v,u); }
    dfs(1,0);
    for(int i=1; i<=n; i++)
    {
        if(p[i]) { ++res; continue; }
        int tmp = e[head[i]].v;
        p[i] = p[tmp]; p[tmp] = i; res += 2;
    }
    cout << res << '\n';
    for(int i=1; i<=n; i++) cout << p[i] << " \n"[i==n];
    return 0;
}