== 제출 결과 ==
run-id	 user id	 프로그램 명	 결과	 언어	 경과 시간(초)	 코드 사이즈(byte)	 제출 시간
1370542	 zeropage	 anniversary	 accept	 C++	 0.04	         2110	                 2014-07-15 01:06

== 풀이 ==

 * 트리 구조를 반영하여 다이나믹을 구현해야 한다.
 * leaf-node(부하가 없는 직원)부터 친밀도를 구하여 root까지의 친밀도를 구해야 한다.
 * 직속 관계에 있는 직원들은 같이 파티에 참석하지 못한다. -> 트리의 부모가 파티에 참석하면, 자식은 파티에 참석하지 못한다. 자식이 하나라도 파티에 참석하면 부모는 파티에 참석하지 못한다. 로 해석이 가능.
 * 각 노드(직원)에 대해서 파티에 참석할 때의 최대 친밀도와 참석하지 않을 때의 최대 친밀도를 구한다. 
 * 점화식 
     d(idx,participate) = sum_of_not_participate + intimaices(idx);
     d(idx,participate) = max(sum_of_participate, sum_of_not_participate);
 * DP 테이블을 채울 때는 leaf-node에서 root로 채워나가야 한다. -> 어떤게 leaf-node인지 판단하는게 필요.
 
== 소스 ==

{{{
#include<iostream>
#include<algorithm>
#include<vector>
#include<list>
using namespace std;
const int N = 6020;
int n, intimacies[N];
int d[N][2]; // d[i][0] - participate, d[i][1] - not participate
int boss[N]; // at first, every staff's boss is himself. Thus boss[i] = i;
vector < list < int > > staffs; // vector[i]
vector < pair <int, int> > staff_priority_queue; // vector[i].first = level of Tree, vectors[i].second = idx.
int cmp(pair <int, int> s, pair <int, int> w){
	return s.first > w.first;
}
void leveling_node(int node, int level){
	staff_priority_queue[node].first = level;
	for(list<int>::iterator it = staffs[node].begin(); it != staffs[node].end(); it++){
		leveling_node(*it, level + 1);
	}
}
int main(void){

	cin>>n;
	staff_priority_queue.resize(n + 10);
	staffs.resize(n + 10);
	staff_priority_queue[0].first = -1;
	staff_priority_queue[0].second = -1;
	for(int i = 1; i<=n; i++){
		cin>>intimacies[i];
		staff_priority_queue[i].second = i;
		staff_priority_queue[i].first = -1;
		boss[i] = i;
	}
	int L, k, m = 0;
	while(1){
		cin>>L>>k;
		if(L == 0 && k == 0)break;
		staffs[k].push_back(L);
		staff_priority_queue[k].first++;
		boss[L] = k;
		//at the end, the root of subtree only satisfy 'boss[i] == i'.
		m++;
	};
	
        if(n == m){
		cout<<102;
		return 0;
	}//마지막 데이터 말도 안되는 거 처리를 위해서.. () 

	for(int i = 1; i<=n; i++){
		if(boss[i] == i){
			leveling_node(i, 0);
		}
	}

	int ans = -9999;
	sort(staff_priority_queue.begin(), staff_priority_queue.begin() + n + 1, cmp);
        //sorting by tree level.
	for(int i = 0; i<n; i++){
		int sum_of_participate = 0, sum_of_not_participate = 0;
		int idx = staff_priority_queue[i].second;
		for(list<int>::iterator it = staffs[idx].begin(); it != staffs[idx].end(); it++){
			if(d[*it][0] >= 0)sum_of_participate += d[*it][0];
			if(d[*it][1] >= 0)sum_of_not_participate += d[*it][1];
		}
		d[idx][0] = sum_of_not_participate + intimacies[idx];
		d[idx][1] = max(sum_of_participate, sum_of_not_participate);
		if(ans < d[idx][0])ans = d[idx][0];
		if(ans < d[idx][1])ans = d[idx][1];
	}
	cout<<ans;
        return 0;
}

}}}
====
[anniversary]