題意簡要的說就是給一棵樹，求其最大權(quán)獨立集。
樹上的問題一般都可以用DP來解決。
設(shè)dp[pos]是以pos為根的最大權(quán)獨立集，那么dp[pos]=max{val[pos]+dp[son[son[pos]]],dp[son[pos]]}
附代碼
1
# include <iostream>
2# include <cstdio>
3# include <vector>
4# include <cstring>
5# define N 10000
6# define max(a,b) ((a)>(b)?(a):(b))
7using namespace std;
8int val[N],dp[N],n;
9vector<int> g[N];
10using namespace std;
11int solve(int pos)
12
{
13
if(dp[pos]!=-1) return dp[pos];
14 else
15
{
16 dp[pos]=0;
17 int total=val[pos];
18 for(int i=0;i<g[pos].size();i++)
19 {
20 dp[pos]+=solve(g[pos][i]);
21 for(int j=0;j<g[g[pos][i]].size();j++)
22 total+=solve(g[g[pos][i]][j]);
23
}
24 dp[pos]=max(dp[pos],total);
25 return dp[pos];
26
27 }
28
}
29int main()
30{
31 scanf("%d",&n);
32 for(int i=1;i<=n;i++)
33 scanf("%d",val+i);
34 while(true)
35 {
36 int now,fa;
37 scanf("%d%d",&now,&fa);
38 if(!now&&!fa) break;
39 g[fa].push_back(now);
40 }
41 memset(dp,-1,sizeof(dp));
42 int total=-1;
43 for(int i=1;i<=n;i++)
44 if(dp[i]==-1)
45 total=max(total,solve(i));
46 printf("%d\n",total);
47 // system("pause");
48 return 0;
49}
50