D. Hamiltonian Spanning Tree

tree, path, mst

출처: Codeforces D. Hamiltonian Spanning Tree

SOL)

x >= y 일 경우

만약 한 정점에서 나머지 모든 정점에 방문할 수 있는 모양이면 y(n-2) + x

아니면  y*(n-1)

x < y 일 때

최대한으로 이용할 수 있는경로의 수를 구하면 된다

배열을 사용하지 않는 방법도 있지만 좀 생각이 필요하다.

[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<climits>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

const int N = 200010;

vector<int> adj[N];
int can[N];
int n, x, y;
int dfs(int here, int pr = -1){
    int res = 0;
    can[here] = 2;
    for (int i = 0; i < adj[here].size(); i++){
        int next = adj[here][i];
        if (next == pr) continue;

        res += dfs(next, here);
        if (can[here] > 0 && can[next] > 0){
            can[here]--;
            can[next]--;
            res++;
        }
    }
    return res;
}

int main(){
    //freopen("input.txt", "r", stdin);

    cin >> n >> x >> y;

    for (int i = 0; i < n-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    if (x >= y) {
        bool check = false;
        for (int i = 1; i <= n; i++){
            if (adj[i].size() == n - 1)
                check = true;
        }
        if (!check){
            cout << 1LL * (n - 1) *y;
        }
        else
            cout << 1LL * (n - 2) *y + x;
    }
    else{

        int use = dfs(1);
        cout << 1LL * use *x + 1LL*(n - use - 1)*y;
    }
    return 0;
}