【题目来源】https://www.luogu.com.cn/problem/T692586【题目描述】给定一棵有 n 个结点的无向树结点编号为 1∼n。每个结点 i 有一个权值 ai可以为负数、零或正数。现在要从这些结点中选出若干个使得1对于树中的每一条边 (u,v)不能同时选中结点 u 和结点 v2所有被选中结点的权值之和尽可能大。请你计算在满足条件的前提下可以得到的最大权值和是多少。【输入格式】第一行一个整数 n表示结点数。第二行包含 n 个整数 a1a2…an表示每个结点的权值。接下来 n−1 行每行两个整数 uv表示在结点 u 和结点 v 之间有一条无向边。保证给定的边构成一棵树。【输出格式】输出一个整数表示在满足“不选相邻点”条件下选出的结点权值和的最大值。【输入样例】51 2 3 4 51 21 33 43 5【输出样例】11【数据范围】对于全部数据1≤n≤20−10^9≤ai≤10^9输入保证是一棵连通无向树。【算法分析】● 树形DP本质上就是在树结构上进行的动态规划。由于树具有天然的递归性质因此我们可以将原问题分解为若干子树上的子问题。首先先分别求解每一棵子树然后再将这些子问题的解逐层向上合并最终得到整棵树的最优解。● 如何把树变成DP能用的样子首先选一个根节点。树原本是无向的因此需要任选一个节点比如 1 号节点作为根从而将无根树转化为有根树。这样一来就能清晰地分辨出每个节点的父节点和子节点。其次用 DFS 递归遍历。由于父节点的状态依赖于子节点的状态所以一般采用后序遍历的顺序先递归处理完所有的子节点最后再处理当前节点本身。最后定义状态要紧扣问题。状态通常写作dp[u][...]其中 u 表示当前节点而方括号里的内容则需根据具体题目来设计——比如“选或不选当前节点”、“当前节点到叶子的最长距离”等等。【算法代码】#includebits/stdc.h using namespace std; typedef long long LL; const int N5e35; vectorint g[N]; LL val[N],dp[N][2]; void dfs(int u,int fa) { dp[u][1]val[u]; dp[u][0]0; for(int v:g[u]) { if(vfa)continue; dfs(v,u); dp[u][1]dp[v][0]; dp[u][0]max(dp[v][0],dp[v][1]); } } int main() { int n; cinn; for(int i1; in; i) cinval[i]; for(int i1; in; i) { int u,v; cinuv; g[u].push_back(v); g[v].push_back(u); } dfs(1,-1); coutmax(dp[1][0],dp[1][1]); return 0; } /* in: 5 1 2 3 4 5 1 2 1 3 3 4 3 5 out: 11 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/155581179https://blog.csdn.net/hnjzsyjyj/article/details/140286717https://blog.csdn.net/hnjzsyjyj/article/details/140309677
 与 GROUP BY 去重统计：5 亿数据量下的性能实测与选型指南)
