Redaksiya

Підвісимо дерево за першу (будь-яку) вершину.

Позначимо G[v] - найменшу кількість вершин якими можемо покрити піддерево з коренем v, якщо вершину v берем NG[v] - найменшу кількість вершин якими можемо покрити піддерево з коренем v, якщо вершину v не берем.

Якщо ми не беремо вершину v, то всіх її дітей маємо взяти обов'язково (бо ребра між v і дітьми лишаться непокриті) отже NG[v] = sum (G[to]). to - всі сини вершини v.

Якщо ми беремо вершину V, то дітей можемо як взяти так і не взяти. Дивимось для кожного сина, чи його оптимальніше взяти чи ні. NG[v] = sum (min(G[to], NG[to])). to - всі сини вершини v.

Отже просто запустимо пошук в глибину (dfs) і під час обходу будемо рахувати значення G[v], NG[v].

відповідь буде min(G[1], NG[1]).


#include <bits/stdc++.h>

using namespace std;

#define DIM 100007

long long G[DIM],NG[DIM];
vector<int> A[DIM];
long long n;

void dfs(int v, int parent) {
    G[v] = 1; //якщо вершину берем - то рахуємо її
    NG[v] = 0; //якщо не берем, то не рахуємо
    for(auto to : A[v]) //перевіряємо всіх дітей
        if(to != parent) {
            dfs(to, v); //запускаємо пошук в глибину для сина
            G[v] += min( G[to], NG[to] ); //якщо вершина V в покритті, то дітей можна як брати так і не брати
            NG[v] += G[to]; //ящо вершина V не в покритті, то синів треба обов'язково взяти (щоб ребра між V і синами були покриті
        }
}

int main()
{
    cin >> n;
    for(int i = 1; i < n; i++) {
        long long v1,v2;
        cin >> v1 >> v2;
        A[v1].push_back(v2);
        A[v2].push_back(v1);
    }

    dfs(1,-1); //приймемо за корінь першу вершину
    cout<<min(G[1], NG[1])<<endl; //мінімум з варіанті коли корінь берем і не берем

    return 0;
}