codeforces 618d 검색

제목: 완전한 그림의 생성 나무, 나무변권과 비나무변권을 제시하고 가장 짧게 한 번씩 지나가도록 한다.
xy일 때, 가능한 한 나무 가장자리가 아닌 것을 선택하면, 국화 모양의 나무만 반드시 한 변을 선택해야 한다는 것을 발견할 수 있습니다.
핸드폰에 프로그램을 걸어서 논문을 제출해 보세요...아프다.키보드가 있지만...
#include <cstdio>
#include <vector>
using namespace std;
const int N = 200005;
vector<int> g[N];
int tree = 0;
int dfs(int u, int fa) {
    int out = 2;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v == fa) continue;
        if (dfs(v, u) && out)
            tree++, out--;
    }
    return out;
}

int main() {
    long long x, y;
    int n, a, b, i;
    scanf("%d%lld%lld", &n, &x, &y);
    for (i = 1; i < n; i++) {
        scanf("%d%d", &a, &b);
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if (x <= y) dfs(1, -1);
    else
        for (i = 1; i <= n; i++)
            if (g[i].size() == n - 1) {
                tree++;
                break;
            }

    printf("%lld", x * tree + y * (n - tree - 1));

    return 0;
}

좋은 웹페이지 즐겨찾기