题目链接：http://acm.ocrosoft.com/problem.php?cid=1695&pid=7

题目描述：人Ural周立大学的校长正在筹备学校的80周年纪念聚会。由于学校的职员有不同的职务级别，可以构成一棵以校长为根的人事关系树。每个职员都有一个唯一的整数编号（范围在1到N之间），并且对应一个参加聚会所获得的欢乐度。为了使每个参加聚会者都感到欢乐，校长想设法使每个职员和他（她）的直接上司不会同时参加聚会。 
    你的任务是设计一份参加聚会者的名单，使总的欢乐度最高。

输入

输入的第一行是一个整数N，1<= N <= 6000 
以下的N行是对应的N个职员的欢乐度（欢乐度是一个从-128到127之间的整数） 
接着是学校的人事关系树，树的每一行格式如下： 
< L > < K > 
表示第K个职员是第L个职员的直接上司。 
输入以0 0表示结束

输出

输出参加聚会者获得的最大总欢乐度

样例输入

7

1

1

1

1

1

1

1

1 3

2 3

6 4

7 4

4 5

3 5

0 0

样例输出

5

题目类型：

树型dp

思路：

这道题是一道典型的树型dp，我们可以这么理解，如果上司没去，下属可以去或不去，如果上司去了，那下属一定不去，因此我们可以从上到下遍历，将所有情况通过dp的形式遍历出来，得到答案

#include <bits/stdc++.h>

#define maxn 6005

using namespace std;

int m,rt,n,u,v;

int w[maxn];//代表权值

int vis[maxn];//标记根节点

vector<int> g[maxn];

int dp[maxn][2];//二维数组的后一维代表去或不去的两种情况

void dfs(int u)

{

dp[u][0]=0;

dp[u][1]=w[u];//将u去或不去的两种情况分别列出

for(int i=0;i<g[u].size();i++)

{

int v=g[u][i];

dfs(v);

dp[u][0]+=max(dp[v][1],dp[v][0]);//上司不去，下属可以去可以不去

dp[u][1]+=dp[v][0];//上司去了，下属一定不去

 }



}

int main()

{

int n;

cin>>n;

for(int i=1;i<=n;i++)

{

cin>>w[i];

 }

 while(~scanf("%d %d",&u,&v))

 {

  if(u==0&&v==0)

  break;

  g[v].push_back(u);//建立父节点对子节点的图

  vis[u]=1;//标记子节点

 }

 for(int i=1;i<=n;i++)

 {

  if(!vis[i])//从根节点开始遍历

 {

  rt=i;

  dfs(rt);

  break;

 }

  }

  cout<<max(dp[rt][0],dp[rt][1]);

  return 0;

}