Arthur公司是一个等级森严的公司，它们有着严格的上司与下属的关系，公司以总裁为最高职位，他有若干个下属，他的下属又有若干个下属，他的下属的下属又有若干个下属……现接近年尾，公司组织团拜活动，活动中有一部分是自由舞会，公司的每个职员都有一个搞笑值，现要你制定一套哪些人上台的方案，使得台上所有演员的搞笑值最大。当然，职员们是不会和他们的顶头上司一起上台的。
第一行一个整数N，表示这个公司总共的职员个数。
接下来一行有N个整数，由空格隔开，第i个整数表示职员i的搞笑值Ai（-1327670≤Ai≤1327670）。
接下来N-1行，每行一个1到N的整数，第i个整数表示职员i+1的顶头上司是谁，当然总裁就是职员1。
一个整数，表示台上所有职员搞笑值之和的最大值。
输入：
7
1 1 1 1 1 1 1
1
1
5
1
4
4
输出：
5
没有上司的舞会问题
#include <iostream> #include <algorithm> #include <vector> using namespace std; const int MAXN=5005; typedef long long ll; int n; int v[MAXN]; vector<int> tree[MAXN]; ll dp[MAXN][2]; void dfs(int u) { dp[u][1]+=v[u]; for(int i=0;i<tree[u].size();i++) { int v=tree[u][i]; dfs(v); dp[u][0]+=max(dp[v][1],dp[v][0]); dp[u][1]+=dp[v][0]; } } int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>v[i]; } for(int i=2;i<=n;i++) { int fa; cin>>fa; tree[fa].push_back(i); } dfs(1); cout<<max(dp[1][0],dp[1][1])<<endl; return 0; }
原文：http://www.cnblogs.com/program-ccc/p/5639609.html