Вершинне покриття#265
Підвісимо дерево за першу (будь-яку) вершину.
Позначимо 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;
}