poj 2342 Anniversary party (基础树形dp)
题意：n个人的上下级关系形成一棵树..每一个人有一个val（可正可负），要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。
思路：树形dp入门题。
dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。
注意dp转移方程是放在每次dfs之后的回溯位置的。。。
这样做的话访问是从根节点到叶子节点，更新就成了从叶子节点到根节点。。。
联想到数字三角形…其实是一样的。。
sad…dp苦手如我也开始刷dp了吗。。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2016年06月24日 星期五 13时07分51秒
4File Name :code/poj/2342.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=6E3+7;
34int n;
35int a[N];
36int in[N];
37vector <int> edge[N];
38
39int dp[N][2];
40int root;
41void debug()
42{
43 for ( int i = 1 ; i <= n ; i++)
44 printf("%d %d %d\n",i,dp[i][0],dp[i][1]);
45}
46void dfs ( int u,int pre)
47{
48
49 // cout<<"u:"<<u<<endl;
50 int siz = edge[u].size();
51 for ( int i = 0 ; i < siz ; i ++)
52 {
53 int v = edge[u][i];
54 if (v==pre) continue;
55
56
57 dfs(v,u);
58 dp[u][0] +=max(dp[v][0],dp[v][1]); //如果父节点没选，那么当前节点可以有两种选择。
59 dp[u][1] +=dp[v][0]; //如果父亲节点选了，那么当前节点只能不选。
60
61
62 }
63}
64int main()
65{
66 #ifndef ONLINE_JUDGE
67 freopen("code/in.txt","r",stdin);
68 #endif
69
70
71 ms(dp,0);
72 ms(in,0);
73 scanf("%d",&n);
74 for ( int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
75
76 int u,v;
77 while (~scanf("%d%d",&u,&v))
78 {
79 if (u==0&&v==0) break;
80 in[u] ++;
81 edge[v].push_back(u);
82 }
83 for ( int i = 1 ; i <= n; i++) if (in[i]==0) root = i ;
84 for ( int i = 1 ; i <= n ; i++) dp[i][1] = a[i];
85
86 dfs(root,-1);
87
88 int mx = -inf;
89 mx = max(dp[root][0],dp[root][1]);
90 debug();
91 printf("%d\n",mx);
92
93
94 #ifndef ONLINE_JUDGE
95 fclose(stdin);
96 #endif
97 return 0;
98}