题意
N个人，每个人都有自己的权值。N-1条边u v（题目说是若干条边，以0 0结尾，但是其实就是N-1条边）表示u是v的直接主管。
选若干个人，要求这些人的权值和最大且没有其直接主管或直接下属同时在。
题解
以1为根建一个有根树，确定每个结点的深度和其子结点。
如果选了u结点，那么u结点的子结点一定不能选。如果没有选u结点，其子结点v可以选也可以不选。
设dp[u][0]表示不选u结点的u子树的最大权独立集，dp[u][1]表示选u结点的u子树的最大权独立集。
那么，
dp[u][0]=sigma max(dp[v][1]，dp[v][0]）。
dp[u][1]=sigma dp[v][0]。
AC代码
#include <bits/stdc++.h>
using namespace std;const int maxn=6e3+7;
int dp[maxn][2];
struct node
{int num,w,dep;bool operator<(const node &o)const{return dep>o.dep;}
}a[maxn];
vector<int> g[maxn];
int deep[maxn];void dfs(int u,int fa,int dep)
{a[u].dep=dep;deep[u]=dep;for(int i=0;i<g[u].size();i++){int v=g[u][i];//printf("%d %d\n",u,v);if(v==fa) continue;dfs(v,u,dep+1);}
}
int main()
{int n;while(~scanf("%d",&n)){for(int i=1; i<=n; i++){scanf("%d",&a[i].w);a[i].num=i;}int u,v;for(int i=0; i<=n; i++)g[i].clear();while(~scanf("%d%d",&u,&v),u||v){//scanf("%d%d",&u,&v);g[u].push_back(v);g[v].push_back(u);}dfs(1,0,1);sort(a+1,a+1+n);memset(dp,0,sizeof(dp));for(int i=1; i<=n; i++){int u=a[i].num;// printf("%d %d\n",u,deep[u]);dp[u][0]=0;dp[u][1]=a[i].w;for(int j=0; j<g[u].size(); j++){int v=g[u][j];if(deep[v]<deep[u])continue;dp[u][0]+=max(dp[v][1],dp[v][0]);dp[u][1]+=dp[v][0];}}int ans=max(dp[1][0],dp[1][1]);printf("%d\n",ans);}return 0;
}