题目描述 Ural大学有N个职员，编号为1~N。他们有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。每个职员有一个快乐指数。现在有个周年庆宴会，要求与会职员的快乐指数最大。但是，没有职员愿和直接上司一起参加宴会。
输入 第一行一个整数N。(1≤N≤6000)
接下来N行，第i+1行表示i号职员的快乐指数Ri。(-128≤Ri≤127)
接下来N-1行，每行输入一对整数L,K。表示K是L的直接上司。
最后一行输入0,0。
输出 第1行：输出最大的快乐指数。
样例输入 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 0 0 样例输出
5
很简单的一个模板，树的最大独立集，想法和紫书上的一样，就是对递归的理解。
多看几遍可以理解。
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<vector> using namespace std; int val[6010]; int f[6010]; int s[6010]; int gs[6010]; int out[6010]; vector<int> son[6010]; int n; void dfs(int z,int fa) { f[z] = fa; int len = son[z].size(); for(int i=0; i<len; i++) { int p = son[z][i]; if(p==fa)continue; dfs(p,z); } return ; } void dp(int z,int fa) { int d = son[z].size(); for(int i=0; i<d; i++) { int p = son[z][i]; if(p!=fa) { dp(p,z); s[z] += out[p]; if(f[z]) gs[ f[z] ] += out[p]; } } out[z] = max(s[z], gs[z]+val[z]); return ; } int main() { cin >> n; for(int i=1; i<=n; i++) cin >> val[i]; int k,l; while(1) { cin >> k >> l; if(k+l==0)break; son[k].push_back(l); son[l].push_back(k); } dfs(1,0); dp(1,0); cout << out[1] << endl; return 0; } 水波
