一道不知道是不是树形dp的水题。。
就是选了一个点不能选他的父亲和儿子。 求一个最大值
见代码
描述
Arthur公司是一个等级森严的公司，它们有着严格的上司与下属的关系，公司以总 裁为最高职位，他有若干个下属，他的下属又有若干个下属，他的下属的下属又有若干个下属……现接近年尾，公司组织团拜活动，活动中有一部分是*舞会，公 司的每个职员都有一个搞笑值，现要你制定一套哪些人上台的方案，使得台上所有演员的搞笑值最大。当然，职员们是不会和他们的顶头上司一起上台的。
格式
输入格式
第一行一个整数N，表示这个公司总共的职员个数。
接下来一行有N个整数，由空格隔开，第i个整数表示职员i的搞笑值Ai（-1327670≤Ai≤1327670）。
接下来N-1行，每行一个1到N的整数，第i个整数表示职员i+1的顶头上司是谁，当然总裁就是职员1。
输出格式
一个整数，表示台上所有职员搞笑值之和的最大值。
提示
【数据范围】
保证100%的数据N≤5000
来源
URAL 由xzx改编
代码：
1 #include <iostream> 2 #include <vector> 3 #include <cstdio> 4 using namespace std; 5 #define MAX 5000+10 6 vector<int> son[MAX]; 7 int fun[MAX]; 8 int N; 9 int dp[MAX][2]; 10 int dfs(int i,int part) 11 { 12 int& d =dp[i][part]; 13 if(d)return d; 14 15 if( part==0) 16 { 17 for(int k=0;k<son[i].size();k++) 18 { 19 d += max(dfs( son[i][k] , 1), dfs(son[i][k],0)); 20 } 21 return d ; 22 } 23 if( part == 1) 24 { 25 for(int k=0;k<son[i].size();k++) 26 { 27 d += dfs(son[i][k],0); 28 } 29 return d= d+fun[i]; 30 } 31 } 32 int main() 33 { 34 scanf("%d",&N); 35 for(int i=1;i<=N;i++) 36 { 37 scanf("%d",&fun[i]); 38 } 39 for(int i=2;i<=N;i++) 40 { 41 int d; 42 scanf("%d",&d); 43 son[d].push_back(i); 44 } 45 printf("%d\n",max(dfs( 1,0),dfs(1,1))); 46 return 0; 47 }