题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1520
题意大致是给出一个隶属关系树，每个人代表一个结点，每个结点都有权值，有父子关系的点对只能选择一个，问怎样使得权值之和最大。
代码如下：
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef unsigned int ui; 4 typedef long long ll; 5 typedef unsigned long long ull; 6 #define pf printf 7 #define mem(a,b) memset(a,b,sizeof(a)) 8 #define prime1 1e9+7 9 #define prime2 1e9+9 10 #define pi 3.14159265 11 #define lson l,mid,rt<<1 12 #define rson mid+1,r,rt<<1|1 13 #define scand(x) scanf("%llf",&x) 14 #define f(i,a,b) for(int i=a;i<=b;i++) 15 #define scan(a) scanf("%d",&a) 16 #define mp(a,b) make_pair((a),(b)) 17 #define P pair<int,int> 18 #define dbg(args) cout<<#args<<":"<<args<<endl; 19 #define inf 0x7ffffff 20 inline int read(){ 21 int ans=0,w=1; 22 char ch=getchar(); 23 while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();} 24 while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar(); 25 return ans*w; 26 } 27 int n,m,t; 28 const int maxn=1e4+10; 29 int value[maxn]; 30 int dp[maxn][2];//0表示这个点不选择的最大权值和，1表示选择这个点的最大权值和 31 vector<int> G[maxn]; 32 int f[maxn];//f的设置是为了查找根节点 33 void dfs(int u) 34 { 35 dp[u][0]=0; 36 dp[u][1]=value[u];//参加和不参加两种情况的初值设置 37 for(int i=0;i<G[u].size();i++) 38 { 39 int son=G[u][i]; 40 dfs(son);//对每一个子节点都进行一次dfs 41 dp[u][0]+=max(dp[son][1],dp[son][0]);//父节点不选择之后子节点可选可不选 42 dp[u][1]+=dp[son][0];//父节点选择之后子节点只能不选择 43 } 44 } 45 int main() 46 { 47 //freopen("input.txt","r",stdin); 48 //freopen("output.txt","w",stdout); 49 std::ios::sync_with_stdio(false); 50 while(~scanf("%d",&n)) 51 { 52 f(i,1,n) 53 { 54 scanf("%d",&value[i]); 55 G[i].clear(); 56 f[i]=-1; 57 } 58 while(1) 59 { 60 int a,b; 61 scanf("%d%d",&a,&b); 62 if(a==0&&b==0)break; 63 G[b].push_back(a); 64 f[a]=b; 65 } 66 int t=1; 67 while(f[t]!=-1) 68 { 69 t=f[t]; 70 } 71 dfs(t); 72 printf("%d ",max(dp[t][0],dp[t][1])); 73 } 74 }