给出一个点数为 \(n\) 的无向完全图，所有边的长度均为 \(y\)，然后指定该图的一个生成树，将树中的长度改为 \(x\)，求该图最短的哈密顿路径的长度。
先分类讨论，对于 \(x\ge y\) 的情况是比较容易处理的。此时需要尽可能少用生成树中的边，注意到树是一个特殊的二分图，它只有 \(n-1\) 条边，而原图中每个点都有 \(n-1\) 条边可以走。容易发现，只有在生成树是一个菊花图的时候至少要用到一条边，否则都可以避免使用树上的边。所以特判一下树的形态即可。
而对于另一种情形，我们需要尽可能多用树上的边，这就相当于一个路径覆盖问题。考虑我们要求的哈密顿路径，它和生成树共用的那些边在树上呈现出若干条分离的链。这其实是一个这样的问题：如何在一棵树上选出尽可能多的边，使它们形成互不相交的链？
一种方法是采用树形 dp，将每个节点能否向上连边作为状态。但是这里的状态转移十分有趣，对于当前子树的根节点，将向上连边的机会直接用掉（即在子树中形成一个完整的、弯曲的路径）总是优于保留这个机会。这种现象很容易得到解释：假设当前节点是 \(u\)，\(v\) 是某个可以与 \(u\) 相连的子节点，而 \(f\) 是 \(u\) 的父亲节点，如果 \(u\) 选择保留这个机会，那么 \(v\) 的机会就被浪费了，并且 \(u\) 可能会抢占它的兄弟节点与父亲相连的机会；而如果它们相连，\(u\) 和 \(v\) 的机会直接得到了兑现，而且 \(f\) 依然有可能与 \(u\) 的兄弟节点相连。因此，直接贪心就可以解决这个问题。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 2e5 + 5;
vector<int> g[maxn];
int edg;
int dfs(int u, int fa) {
int cnt = 0;
for (auto v : g[u]) {
if (v == fa)
continue;
if (dfs(v, u) > 0)
cnt++;
}
if (cnt >= 2) {
edg += 2;
return 0;
}
edg += cnt;
return 1;
}
void solve() {
int n, x, y;
cin >> n >> x >> y;
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
g[u].push_back(v), g[v].push_back(u);
}
if (x >= y) {
bool star = false;
for (int i = 1; i <= n; ++i) {
if ((int)g[i].size() == n - 1)
star = true;
}
ll ans = 1LL * y * (n - 1);
if (star)
ans = ans - y + x;
cout << ans << endl;
return;
}
edg = 0;
dfs(1, 0);
ll ans = 1LL * x * edg + 1LL * y * (n - 1 - edg);
cout << ans << endl;
}
int main(int argc, char **argv) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}