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;
}