NTPFECT - Đại diện hoàn hảo
Tác giả: hieult
Ngôn ngữ: C++
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
//#include<conio.h>
#define ep 0.000000001
#define maxn 10011
#define oo 1111111111
#define base 100000000
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
double const PI=4*atan(1);
using namespace std;
typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
VVI V;
int f[1111][3],flag,cha[1111],la[1111];
void duyet(int u,int mau){
if(f[u][mau]>-1) return;
if(la[u]){
f[u][0] = 1;
f[u][1] = 1;
f[u][2] = 0;
}
f[u][mau] = mau%2;
int MIN = oo;
TR(V[u],it){
int v = *it;
if(cha[u]!=v)
{
cha[v] = u;
if(mau%2==0)
{
duyet(v,1);
duyet(v,0);
f[u][mau]+=min(f[v][1],f[v][0]);
}
else{
duyet(v,1);
duyet(v,2);
f[u][mau]+=min(f[v][1],f[v][2]);
}
if(!mau){
MIN = min(MIN,f[v][1]-f[v][0]);
}
}
}
if(!mau && MIN>0 && (V[u].size()>1||u==1))
f[u][mau]+=MIN;
// printf("%d %d %d %d\n",u,mau,f[u][mau],MIN);
}
int main(){
// freopen("NTPEFECT.in","r",stdin);
int n,u,v;
while(scanf("%d",&n)>0 && n>0){
if(n==1){
printf("1\n");
continue;
}
memset(f,-1,sizeof(f));
memset(cha,0,sizeof(cha));
memset(la,0,sizeof(la));
V.clear();
V.resize(n+2);
for(int i = 1;i<n;i++){
scanf("%d %d",&u,&v);
V[u].push_back(v);
V[v].push_back(u);
}
for(int i = 2;i<=n;i++) if(V[i].size()==1) la[i]=1;
duyet(1,0); duyet(1,1);
printf("%d\n",f[1][0]<f[1][1]?f[1][0]:f[1][1]);
}
// getch();
}