CodeForces 618D Hamiltonian Spanning Tree

Posted on By 二价氢

题目大意

给一个完全图和它的一个生成树,在数上行走需要费用\(x\),在其余的边上行走需要费用\(y\),问现在要找一条汉密尔顿路,使得费用最小。

做法

为了方便起见,下面将生成树上的边称作“树边”,将图上的其它边称作“非树边”

考虑\(x < y\)的情况,显然应该尽量减少非树边(因为每一条树边贡献\(x\),每一条非树边贡献\(y\)),显然我们可以用树状DP来解决这个经典的树上路径覆盖问题,用\(f_{x,y}\)表示点\(x\)在状态\(y\)的答案即可

然而,我们可以也用贪心解决这个问题,考虑一个非叶子结点,如果它能向下连边,那么向下连边显然是答案不变差的选择,因而,记录每个结点可以向下连边的个数\(available_i\),以及儿子个数\(son_i\),如果\(available_i<2\),那么父亲可以向它连边,否则父亲不能向它连边,这样这个结点对答案的贡献就是\((son_i - available_i) + \max(0, available_i - 2)\),DFS一次即可

考虑\(x > y\)的情况,显然走非树边是最优的,这里需要注意一类特殊情况,即这个树是一棵菊花树,这样我们不可避免地会走一条树边,可以证明,其余的情况都可以只走非树边。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 200000 + 2;
vector<int> e[maxn];
int n, an;
long long x, y;
int dfs(int nd, int fa) {
    int sc = 0, nsc = 0;
    for (int nx : e[nd]) {
        if (nx == fa) continue;
        int tnsc = dfs(nx, nd);
        sc++;
        if (tnsc <= 1) nsc++;
    }
    an += sc - nsc + max(0, nsc - 2);
    return nsc;
}
int main() {
    ios::sync_with_stdio(0);
    int tu, tv, flg = 0;
    cin >> n >> x >> y;
    for (int i = 1; i < n; i++) {
        cin >> tu >> tv;
        e[tu].push_back(tv);
        e[tv].push_back(tu);
    }
    for (int i = 1; i <= n; i++)
        if (int(e[i].size()) == n - 1) flg = true;
    if (x >= y) {cout << (flg ? x + y * (n - 2) : y * (n - 1)) << endl;return 0;}
    dfs(1, -1);
    cout << an * y + (n - 1 - an) * x << endl;
    return 0;
}