UVa1218 Perfect Service

약간 복잡한 나무형 dp.상태의 유형은 현재 노드뿐만 아니라 현재 노드의 부 노드와도 관계가 있다.모두 세 가지 상태가 있는데 현재 노드는 서버이고 현재 노드가 아니며 부 노드가 아니며 현재 노드가 아니며 부 노드가 아니다.dp를 할 때 불가능한 상태의 비용을 무한대로 둔다. 이렇게 구한 해답은 불가능한 상태가 되지 않는다.

#include <iostream>    
#include <stdio.h>    
#include <cmath>    
#include <algorithm>    
#include <iomanip>    
#include <cstdlib>    
#include <string>    
#include <memory.h>    
#include <vector>    
#include <queue>    
#include <stack>    
#include <map>  
#include <set>  
#include <ctype.h>    
#define INF 10000
#define ll long long
#define max3(a,b,c) max(a,max(b,c))
#define MAXN 100010

using namespace std;  

vector<int> E[10010];
int dp[10010][3];

/*
 * 0    
 * 1    
 * 2    
 */
int fun(int u,int f,int type){
	if(dp[u][type]!=-1)return dp[u][type];
	 
	int re=0;
	if(type==1){
		for(int i=0;i<E[u].size();i++){
			if(E[u][i]==f)continue;
			re+=min(fun(E[u][i],u,1),fun(E[u][i],u,2));
		}
		re++;
	}
	if(type==0){
		int tmp=0;re=INF;
		for(int i=0;i<E[u].size();i++){
			if(E[u][i]==f)continue;
			tmp+=fun(E[u][i],u,0);
		}
		//     
		for(int i=0;i<E[u].size();i++){
			if(E[u][i]==f)continue;
			re=min(re,tmp-fun(E[u][i],u,0)+fun(E[u][i],u,1));
		}
		if(E[u].size()==1&&f!=-1)re=INF;
	}
	if(type==2){
		for(int i=0;i<E[u].size();i++){
			if(E[u][i]==f)continue;
			re+=fun(E[u][i],u,0);
		}
	}
	
	dp[u][type]=re;
	return re;
}

int main(){
	int N;
	while(cin>>N){
		memset(dp,-1,sizeof(dp));
		for(int i=1;i<=N;i++)E[i].clear();
		int u,v;
		for(int i=1;i<N;i++){
			cin>>u>>v;
			E[u].push_back(v);
			E[v].push_back(u);
		}
		cout<<min(fun(1,-1,0),fun(1,-1,1))<<endl;
		int end;
		cin>>end;
		if(end==-1)break;
	}
	return 0;
}