P1352

原题链接 题解 dp的核心在于，增加一颗根节点时，以其为根节点的$ ans = max( \sum_{}^{}子节点不选 + r[new],max(\sum_{}^{}子节点选 , \sum_{}^{}子节点不选) ) $ code #include<bits/stdc++.h> using nam ......

考察算法：树形 \(DP\)。 题目概述 给你一个树，每个结点有一个“上司”。每个节点都有一个快乐指数 \(h_i\)。 但是，如果有某个节点的上司(父亲)，已经来到了舞会，那么它的儿子就不能去了。 求：最大的快乐指数（所有人的快乐指数之和）。 思路 树形 \(DP\)。设 \(f_{i,0}\) ......

分析 树形 dp。 定义状态 \(dp_{~i,~0}\) 为在以 \(i\) 为根节点的子树中，不选第 \(i\) 个人的最大快乐值，\(dp_{~i,~1}\) 为在以 \(i\) 为根节点的子树中，选第 \(i\) 个人的最大快乐值。 寻找根节点，然后从根节点开始 dfs，当前节点 \(u\) ......

[Problem](https://www.luogu.com.cn/problem/P1352) ### Solution 经典树上dp。 我们发现一个节点统计 or不统计答案影响下一级，所以dp时需要加上这个状态。 树上dp虽然名义上叫dp，但一般是基于记忆化搜索实现（ 第二层状态就统计以其为根 ......