【题目大意】
有n个职员，编号为1～n，他们之间的关系就像一棵数，父节点是子结点的直接上司，每个职员有一个快乐指数$H_i$，，且所有职员都不愿意跟自己的直接上司一起参加舞会，求所有参加舞会的职员的快乐指数最大值。
【思路分析】
设f[i][0]表示编号为i的结点不参加舞会时，以i结点为根的子树的快乐指数最大值；f[i][1]表示i结点参加舞会时，以i结点为根的子树的快乐指数最大值，易得转移方程：$$f[i][0]=sum_{xin son[i]}max(f[x][0],f[x][1])$$
$$f[i][1]=H[i]+sum_{xin son[i]}f[x][0]$$其中son[i]表示i结点的子结点集合。
【代码实现】
1 #include<bits/stdc++.h> 2 #define rg register 3 #define go(i,a,b) for(rg int i=a;i<=b;i++) 4 #define back(i,a,b) for(rg int i=a;i>=b;i--) 5 #define ll long long 6 #define mem(a,b) memset(a,b,sizeof(a)) 7 using namespace std; 8 const int N=10002; 9 vector<int> son[N]; 10 int f[N][2],h[N],n,fa[N]; 11 void dp(int x){ 12 f[x][0]=0;f[x][1]=h[x]; 13 int size=son[x].size(); 14 go(i,0,size-1){ 15 int y=son[x][i]; 16 dp(y); 17 f[x][0]+=max(f[y][1],f[y][0]); 18 f[x][1]+=f[y][0]; 19 } 20 return; 21 } 22 int main(){ 23 scanf("%d",&n); 24 go(i,1,n) scanf("%d",&h[i]); 25 go(i,1,n-1){ 26 int x,y; 27 scanf("%d%d",&x,&y); 28 fa[x]=y; 29 son[y].push_back(x); 30 } 31 int root; 32 go(i,1,n) if(!fa[i]){root=i;break;} 33 dp(root); 34 printf("%d ",max(f[root][1],f[root][0])); 35 return 0; 36 }