1435. PT07X - Vertex Cover

You are given an unweighted, undirected tree. Write a program to find a vertex set of minimum size in this tree such that each edge has as least one of its end-points in that set.

Input. The first line contains one integer n (0 < n ≤ 100000) – number of nodes in the tree. Next n – 1 lines contain n – 1 edges of that tree. Each line contains a pair (u, v) means there is an edge between node u and node v (1 ≤ u, v ≤ n).

Output. Print number of nodes in the satisfied vertex set on one line.

Sample Input

3

1 2

1 3

Sample Output

1

РЕШЕНИЕ

динамика на деревьях

Анализ алгоритма

Рассмотрим поддерево с вершиной v:

· Если вершина v включается в подмножество, то ее сыновья могут быть или включены, или не включены в искомое подмонжество.

· Если вершина v не включается в подмножество, то ее сыновья обязательно должны быть включены в искомое подмонжество.

Реализация алгоритма

#include <cstdio>

#include <vector>

#include <cstring>

#define MAX 100002

using namespace std;

vector<vector<int> > tree;

int i, n, u, v;

// dp[i][] = min number of colored nodes in the satisfied vertex set

// where set = subtree with root i

// dp[i][0] = answer is vertex i is not coverred

// dp[i][1] = answer is vertex i is coverred

int dp[MAX][2];

int dfs(int v, int Parent, int IsCovered)

{

int i, &res = dp[v][IsCovered];

if(res != -1) return res;

if(IsCovered)

// if v is Covered, to can be either covered of not covered

for(res = 1, i = 0; i < tree[v].size(); i++)

{

int to = tree[v][i];

if (to != Parent)

res += min(dfs(to, v, 0),dfs(to,v,1));

}

else

// if v is not Covered, to must be covered

for(res = i = 0; i < tree[v].size(); i++)

{

int to = tree[v][i];

if (to != Parent)

res += dfs(to, v, 1);

}

return res;

}

int main(void)

{

scanf("%d",&n);

tree.resize(n+1);

for(i = 0; i < n - 1; i++)

{

scanf("%d %d",&u,&v);

tree[u].push_back(v);

tree[v].push_back(u);

}

memset(dp,-1,sizeof(dp));

int res = min(dfs(1,-1,1),dfs(1,-1,0));

printf("%d\n",res);

return 0;

}