[POJ] 3659 셀 폰 네트워크 트리의 극소 지배 집합 - 트리 DP

Cell Phone Network
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 5524
Accepted: 1984
Description
Farmer John has decided to give each of his cows a cell phone in hopes to encourage their social interaction. This, however, requires him to set up cell phone towers on his N (1 ≤ N ≤ 10,000) pastures (conveniently numbered 1..N) so they can all communicate.
Exactly N-1 pairs of pastures are adjacent, and for any two pastures A and B (1 ≤ A ≤ N; 1 ≤ B ≤ N; A ≠ B) there is a sequence of adjacent pastures such that A is the first pasture in the sequence and B is the last. Farmer John can only place cell phone towers in the pastures, and each tower has enough range to provide service to the pasture it is on and all pastures adjacent to the pasture with the cell tower.
Help him determine the minimum number of towers he must install to provide cell phone service to each pasture.
Input
* Line 1: A single integer: N * Lines 2..N: Each line specifies a pair of adjacent pastures with two space-separated integers: A and B
Output
* Line 1: A single integer indicating the minimum number of towers to install
Sample Input

5
1 3
5 2
4 3
3 5

Sample Output

2

Source
USACO 2008 January Gold 전송문: [POJ] 3659 Cell Phone 네트워크 제목 분석: 나무의 극소 지배 집합인 나무형 DP 구해.pp[0][i]는 노드 i가 지배 집합에 속하고 하위 노드가 모두 덮일 때의 최소 지배 집합 크기를 나타낸다.pp[1][i]는 노드 i가 지배 집합에 속하지 않지만 이 노드가 노드에 덮여 있고 하위 노드가 모두 덮일 때의 최소 지배 집합 크기를 나타낸다.pp[2][i]는 노드 i가 지배 집합에 속하지 않고 이 노드가 노드에 덮이지 않고 하위 노드가 모두 덮일 때의 최소 지배 집합 크기를 나타낸다.현재 노드가 u이고 u의 하위 노드가 v이면 dp[0][u] =sigma {min {dp[0], dp[1]v], dp[2]v]}} + 1;dp[ 1 ][ u ] = sigma { min { dp[ 0 ][ v ] , dp[ 1 ][ v ] } ; dp[ 2 ][ u ] = sigma { dp[ 1 ][ v ] } ; 그 중에서 dp[1][u]에서 선택한 하위 노드에 최소한 하나의 지배 집합에 속하는 노드가 포함되어야만 조건에 부합된다. 그렇지 않으면 dp[1]u]=INF를 설정하고 모든 dp[1]v]에 조건에 부합되지 않는 해가 존재할 때 dp[2]u]=INF. (여기에 모든 INF를 설정하면 조건에 부합되지 않는 해를 표시한다).만약에 우리가 그 중의 한 노드를 뿌리 결점 루트로 선택한다면 답은min {dp[0]root], dp[1]root]}이다.이 때 뿌리 결점은 반드시 덮어써야 하기 때문에 dp[2][root]가 포함되지 않습니다.코드는 다음과 같습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REPV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define clear( a , x ) memset ( a , x , sizeof a )

const int MAXN = 100005 ;
const int MAXE = 200005 ;
const int INF = 100005 ;

struct Edge {
	int v , n ;
	Edge ( int var = 0 , int next = 0 ) :
		v ( var ) , n ( next ) {}
} ;

Edge edge[MAXE] ;
int adj[MAXN] , cntE ;
int dp[3][MAXN] ;
int n ;

void addedge ( int u , int v ) {
	edge[cntE] = Edge ( v , adj[u] ) ;
	adj[u] = cntE ++ ;
	edge[cntE] = Edge ( u , adj[v] ) ;
	adj[v] = cntE ++ ;
}

void dfs ( int u , int p ) {
	dp[0][u] = 1 ;
	dp[1][u] = 0 ;
	dp[2][u] = 0 ;
	int flag = 0 , flag2 = 0 ;
	for ( int i = adj[u] ; ~i ; i = edge[i].n ) {
		int v = edge[i].v ;
		if ( v == p )
			continue ;
		dfs ( v , u ) ;
		dp[0][u] += min ( dp[0][v] , min ( dp[1][v] , dp[2][v] ) ) ;
		if ( dp[0][v] <= dp[1][v] ) {
			dp[1][u] += dp[0][v] ;
			flag = 1 ;
		}
		else dp[1][u] += dp[1][v] ;
		dp[2][u] += dp[1][v] ;
		if ( dp[1][v] == INF )
			flag2 = 1 ;
	}
	if ( !flag )
		dp[1][u] = INF ;
	if ( flag2 )
		dp[2][u] = INF ;
}

void work () {
	int u , v ;
	while ( ~scanf ( "%d" , &n ) ) {
		clear ( adj , -1 ) ;
		cntE = 0 ;
		REP ( i , n - 1 ) {
			scanf ( "%d%d" , &u , &v ) ;
			addedge ( u , v ) ;
		}
		dfs ( 1 , 0 ) ;
//		REPF ( i , 1 , n )
//			printf ( "%d %d %d
" , dp[0][i] , dp[1][i] , dp[2][i] ) ;
		printf ( "%d
" , min ( dp[0][1] , dp[1][1] ) ) ;
	}
}

int main () {
	work () ;
	return 0 ;
}