题解：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。

分析：

常规想法

根据树的背景和 P_i, P_j 两两不相邻的条件，不难想到方法：常规树状 DP 求最大值。

状态：dp_{i, 0/1} 表示以 i 为根的子树中，选或不选 i 的最大点权和；\ \ 答案：\max dp_{1, 0}, dp_{1, 1}；\ \ 初始状态：dp_{i, 1} = V_i

对于 P_i, P_j 不能相邻，当转移时选了 cur 这个点，则他的子节点 nxt 和父节点 fa 都不能选，由于从下到上递归，无需考虑 fa 节点。

然而，对于同一深度内只能有一个 P_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;