【题目来源】https://www.luogu.com.cn/problem/P1352【题目描述】Ural 大学有 N 名职员编号为 1∼N。他们的关系就像一棵以校长为根的树父节点就是子节点的直接上司。每个职员有一个快乐指数用整数 Hi 给出其中 1≤i≤N。现在要召开一场周年庆宴会不过没有职员愿意和直接上司一起参会。在满足这个条件的前提下主办方希望邀请一部分职员参会使得所有参会职员的快乐指数总和最大求这个最大值。【输入格式】第一行一个整数 N。接下来 N 行第 i 行表示 i 号职员的快乐指数 Hi。接下来 N−1 行每行输入一对整数 L,K表示 K 是 L 的直接上司。【输出格式】输出最大的快乐指数。【数据范围】1≤N≤6000,−128≤Hi≤127【输入样例】711111111 32 36 47 44 53 5【输出样例】5【算法分析】● 此题是树形动态规划的经典习题也是树上最大权独立集简单题。1状态定义f[u][0]不选 u 时以 u 为根的子树最大权。f[u][1]选 u 时以 u 为根的子树最大权。2转移方程u当前子树的根节点vu 的所有直接子节点val[u]节点 u 的权值f[u][0] Σ max(f[v][0], f[v][1])f[u][1] val[u] Σ f[v][0]● 解此题要掌握图的邻接表表示方法。图的邻接表表示可以利用STL vector 或数组模拟实现。由于树是特殊的图所以图的邻接表表示方法完全适用于树。由于树的遍历从树根开始而此题没有明确指明树根所以需要编码判断哪个结点是树根。【算法代码】#includebits/stdc.h using namespace std; const int N6e35; vectorint g[N]; int val[N]; int f[N][2]; bool is_root[N]; int n,root; void dfs(int u,int fa) { f[u][0]0; f[u][1]val[u]; for(int v:g[u]) { if(vfa) continue; dfs(v,u); f[u][0]max(f[v][0],f[v][1]); f[u][1]f[v][0]; } } int main() { memset(is_root,true,sizeof is_root); cinn; for(int i1; in; i) cinval[i]; for(int i1; in; i) { int u,v; cinuv; g[v].push_back(u); is_root[u]false; } for(int i1; in; i) { if(is_root[i]) rooti; } dfs(root,0); coutmax(f[root][0],f[root][1])endl; return 0; } /* in: 7 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5 out: 5 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/119890782https://www.freesion.com/article/7280566554/