[CF1387B1] Village (Minimum) - 贪心,树形dp

技术文章 1年前 (2020) 完美者
2,057 0

标签:重复   必须   lse   min   const   namespace   line   minimum   sig   

Description

给定一棵树,树上每个结点刚开始有一个人,现在每个人需要走到一个不同于原来的结点,并且必须保证每个结点上仍然有且仅有一个人,在树上走一条边的代价为 \(1\),求最小代价。

Solution

考虑这样一个过程,我们递归处理掉这棵树上的所有叶子结点,如果它们还没有移动的话,将它和它的父亲换,此时代价增加 \(2\),然后删除这个结点。重复下去,直到树为空。注意当只剩下根结点的时候,它如果没有被换过,那我们只需要挑它的任意一个孩子跟它换即可。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

int n, m, t1, t2, t3, a[N], ans;
vector<int> g[N];

void dfs(int p, int fa)
{
    for (int q : g[p])
        if (q != fa)
            dfs(q, p);
    if (a[p] == p)
    {
        ans += 2;
        if (fa)
            swap(a[p], a[fa]);
        else
            swap(a[p], a[g[p][0]]);
    }
}

signed main()
{
    ios::sync_with_stdio(false);

    cin >> n;
    for (int i = 1; i < n; i++)
        cin >> t1 >> t2, g[t1].push_back(t2), g[t2].push_back(t1);

    for (int i = 1; i <= n; i++)
        a[i] = i;

    dfs(1, 0);

    cout << ans << endl;
    for (int i = 1; i <= n; i++)
        cout << a[i] << " ";
}

[CF1387B1] Village (Minimum) - 贪心,树形dp

标签:重复   必须   lse   min   const   namespace   line   minimum   sig   

原文地址:https://www.cnblogs.com/mollnn/p/13931639.html

版权声明:完美者 发表于 2020-11-06 2:09:44。
转载请注明:[CF1387B1] Village (Minimum) - 贪心,树形dp | 完美导航

暂无评论

暂无评论...