618D - Hamiltonian Spanning Tree - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mx = 2e5+5;
ll n, x, y, deg[mx], dp[mx][2];
vector<ll> adj[mx];

void dfs(int cur, int prev) {
    ll sm = 0;
    vector<ll> ch(2);
    for (int nxt: adj[cur]) if(nxt != prev) {
        dfs(nxt, cur);
        sm += dp[nxt][0];
        ch.push_back(dp[nxt][1] - dp[nxt][0]);
    }
    nth_element(ch.begin(), ch.begin()+1, ch.end());
    dp[cur][1] = sm + ch[0];
    dp[cur][0] = 1 + sm + ch[0] + ch[1];
}

int main() {
    cin >> n >> x >> y;
    for (int i=1; i<n; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        deg[u]++, deg[v]++;
    }
    if (x >= y) {
        for (int i=1; i<=n; i++) {
            if (deg[i] == n-1) {
                cout << x + (n-2) * y << "\n";
                return 0;
            }
        }
        cout << (n-1) * y << "\n";
        return 0;
    }
    dfs(1, 0);
    cout << ((dp[1][0] - 1) * y) + ((n-dp[1][0]) * x) << "\n";
}