题解：P12382 [蓝桥杯 2023 省 Python B] 树上选点

题意：

在一棵树上找若干个点 $P_i$，保证这些点两两不相邻（不存在有边直接相连），同一深度只选一个点。

目标：求出 $\max \sum V_i$。

数据范围：$1 \le n \le 2 \times 10^5, 1 \le V_i \le 10^4$。

分析：

常规想法

状态：$dp_{i, 0/1}$ 表示以 $i$ 为根的子树中，选或不选 $i$ 的最大点权和；

答案：$\max dp_{1, 0}, dp_{1, 1}$；

初始状态：$dp_{i, 1} = V_i$

换思路想法

有一些题目是两个考虑方向都正确的，如 Peaks，可以优先处理每个询问的 $x$，也可以优先预处理边权。

最终想法

状态：$dp_i$ 表示选了 $i$ 的最大点权和；

答案：$\max dp_i$；

转移：按深度上往下转移，每次取上一层最大的值进行转移，在要注意不能是父节点，所以要维护一个次大值，如果最大值是父节点，那么就继承次大值。总之就是 $dp_i = V_i + \max\limits_{j \ne fa_i} dp_j$。

初始状态：$dp_i = 0$。

总结

代码（部分）

// 继承上一层的最大值，次大值 
int tpmaxi = maxi, tpcmaxi = cmaxi;
for(auto nxt : point[d]) // 枚举深度为d的点
{
	if(dp[fa[cur]] < maxi) dp[cur] = maxi + v[cur];
	else dp[cur] = cmaxi + v[cur];
	// 更新这一层临时的最大值，次大值 
	if(dp[cur] > tpmaxi) tpcmaxi = tpmaxi, tpmaxi = dp[cur];
	else if(dp[cur] > tpcmaxi) tpcmaxi = dp[cur];
} 
// 刷新上一层到这一层的最大值，次大值
maxi = tpmaxi, cmaxi = tpcmaxi;