POJ 2342 Anniversary party （树形DP入门）
题意：
给定一个上下属的关系树， 每个人有一个活跃值， 现在要参加一个派对， 每个人都不会和自己的上属参加派对（上属参加了，下属就不能参加了）， 求参加派对的最大活跃值
分析：
枚举每个节点取与不取得最大值， 从叶子往根推。
#include<cstdio> #include<iostream> #include<cstring> using namespace std; const int maxn = 6007; int dp[maxn][2]; // dp[i][state] 表示i节点 去/不去 分别的最大值 int father[maxn]; //记录每个节点父亲 int vis[maxn]; int N; int root = 0; void dfs(int node){ vis[node] = 1; for(int i = 1; i <= N; i++){ if(vis[i] == -1 && father[i] == node){ dfs(i); dp[node][1] += dp[i][0];//node去， 则i不能去 dp[node][0] += max(dp[i][1], dp[i][0]);// node不去， 比较一下两者最大值 } } } int main() { while(cin >> N) { for(int i = 1; i <= N; i++) cin >> dp[i][1]; for(int i = 1; i <= N; i++){ int u , v; cin >> v >> u; if(v == 0 && u == 0) break; root = u; father[v] = u; } memset(vis, -1, sizeof(vis)); dfs(root); cout << max(dp[root][0], dp[root][1]) << " "; } return 0; }