poj 2342 트리 dp (입문 문제)

There is going to be a party to celebrate the 80-th Anniversary of the Ural State University. The University has a hierarchical structure of employees. It means that the supervisor relation forms a tree rooted at the rector V. E. Tretyakov. In order to make the party funny for every one, the rector does not want both an employee and his or her immediate supervisor to be present. The personnel office has evaluated conviviality of each employee, so everyone has some number (rating) attached to him or her. Your task is to make a list of guests with the maximal possible sum of guests' conviviality ratings.
Input
Employees are numbered from 1 to N. A first line of input contains a number N. 1 <= N <= 6 000. Each of the subsequent N lines contains the conviviality rating of the corresponding employee. Conviviality rating is an integer number in a range from -128 to 127. After that go N – 1 lines that describe a supervisor relation tree. Each line of the tree specification has the form:
L K
It means that the K-th employee is an immediate supervisor of the L-th employee. Input is ended with the line
0 0
Output
Output should contain the maximal sum of guests' ratings.
Sample Input

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0

Sample Output

5

제목: 회사에서 파티를 열고 직원을 초대하지만 모든 직원은 자신의 직접 상사와 함께 참가하는 것을 좋아하지 않기 때문에 상사가 가면 그의 직계 부하들은 갈 수 없고 반대로 갈 수 있다.모든 직원은 흥분치가 있고 회사가 하고자 하는 파티의 흥분치는 가능한 한 크다.
사고방식: 인터넷에서 검색한 블로그는 처음으로 트리 dp를 접하여 트리 dp의 사고를 형성하지 못했다. 이 문제의 방법은 귀속적으로 쓴 것으로 이해가 비교적 좋고 트리 dp의 입문 문제이기도 하다.
비교적 이해하기 쉽다.
dp[i][j], i는 노드를 표시하고 j는 상태를 표시하며 j=1시에는 i가 참가하고 j=0시에는 참가하지 않는다는 뜻이다.
AC 코드:

#include 
#include 
#include 
using namespace std;
int father[6100];
int dp[6100][2];
int book[6100];
int num[6100];
int n,m; 
void dfs(int node)
{
	book[node]=1;
	for(int i=1;i<=n;i++)
	{
		if(!book[i]&&father[i]==node)
		{
			dfs(i);
			dp[node][1]+=dp[i][0];  //       ，     
			dp[node][0]+=max(dp[i][1],dp[i][0]);
			//        ，           
		}
	}
}
int main()
{
	while(~scanf("%d",&n))
	{
		memset(dp,0,sizeof(dp));
		for(int i=1;i<=n;i++)
		scanf("%d",&dp[i][1]);
		
		for(int i=1;i<=n;i++)
        father[i]=i;
        
		int x,y,root;
		while(scanf("%d %d",&x,&y)&&(x+y))
			father[x]=y;
		for(int i=1;i<=n;i++)
		if(father[i]==i)
		{
		  root=i;
		  break;
		}
		memset(book,0,sizeof(book));
	//	printf("%d
",root);
		dfs(root);
		int term=dp[root][1]>dp[root][0]?dp[root][1]:dp[root][0];
		
		printf("%d
",term);
	}
	return 0;
}