Anniversary party
题目链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1520
题意：
公司里有一堆人再开派对，每个人有一个欢乐值，这些人之间有一些上下级关系，每个人都不想和他的直接上司（即是父亲，不包括祖先）同时出现在party上，求party上最大的欢乐值的合。
题解：
由题意知公司成员之间可以组成一些关系树，设value[x]为以x为根节点的子树的最大权值合，child[x]为x的子节点，从树上可以看出，value[x]=max(value[x]+∑value[child[child[x]]]，∑value[child[x]])
代码
#include<stdio.h>
#include<vector>
using namespace std;
const int N=6001;
vector<int>q[N];
int value[N];
bool in[N],mark[N];
int mmax(int x,int y)
{
return x>y?x:y;
}
int dfs(int x)
{
if(mark[x])return value[x];
int v=0,w=0,t;
for(int i=0;i<q[x].size();++i)
{
t=q[x][i];
v+=dfs(t);
for(int j=0;j<q[t].size();++j)
w+=dfs(q[t][j]);
}
value[x]=mmax(value[x]+w,v);
mark[x]=true;
return value[x];
}
int main()
{
int n,res,x,y;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;++i)
{
scanf("%d",&value[i]);
q[i].clear();
in[i]=mark[i]=false;
}
while(~scanf("%d%d",&x,&y)&&x&&y)
{
q[y].push_back(x);
in[x]=true;
}
res=0;
for(int i=1;i<=n;++i)
if(!in[i])res+=dfs(i);
printf("%d
",res);
}
}