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

· · 题解

前言

很不寻常的树形 dp，调了我两小时。

思路

先看第二点要求：任意两点 P_x,P_y 到根的距离不相同。
意思就是说选的点的深度必须互不相同，即树的每一层最多只能选 1 个点。

再看第一点要求：任意两点 P_x,P_y 不相邻，也就是说选了儿子就不能选父亲。

显然层是状态，我们应当从叶子开始，逐步递推到根。
我设计 dp_{i,j} 表示选择了第 i 层的第 j 个点时，最大点权和。特别地，dp_{i,0} 表示不在第 i 层选点。

接下来考虑转移，比较简单。如果我们想选第 i 层的第 j 个点，那么它的儿子都不能选。
如果把第 i+1 层的所有点都依照 dfs 序排出来，那么它的儿子们是连续的一段区间。于是转移的时候，就是在整个序列中扣掉它的“儿子区间”，求最大值。
这可以用前后缀最大值来解决。

无论是 dfs 预处理，还是 dp 过程，每个点都只会被处理常数次，所以时间复杂度为 O(n)。

代码

#include<bits/stdc++.h>
using namespace std;
int n;
vector<int>dp[200003];//[点的深度][深度为i的点中选的哪个点] 
vector<int>edg[200003];
vector<int>rid[200003];//第i层第j个点的原始编号是多少 
int v[200003];
int id[200003],idl[200003];
//在深度为i的点中的编号，深度为i的点的数量 
int lr[200003][2];
int depmax;

void dfs(int p,int dep){
    id[p]=++idl[dep];
    if(rid[dep].size()==0)rid[dep].push_back(0);
    rid[dep].push_back(p);
    for(auto i:edg[p]){
        dfs(i,dep+1);
        if(!lr[p][0])lr[p][0]=id[i];
        lr[p][1]=id[i];
    }
    depmax=max(depmax,dep);
}

int mx[2][200003];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=2;i<=n;i++){
        int f;cin>>f;
        edg[f].push_back(i);
    }
    for(int i=1;i<=n;i++)cin>>v[i];
    dfs(1,1);
    for(int i=0;i<=depmax;i++){
        for(int j=0;j<=idl[i];j++)dp[i].push_back(0);
    }
    for(int i=0;i<=idl[depmax];i++){
        dp[depmax][i]=v[rid[depmax][i]];
    }

    for(int i=depmax-1;i>0;i--){
        for(int j=1;j<=idl[i+1];j++)mx[0][j]=mx[1][j]=0;
        mx[0][1]=dp[i+1][1];
        for(int j=2;j<=idl[i+1];j++)mx[0][j]=max(mx[0][j-1],dp[i+1][j]);//前缀最大值

        mx[1][idl[i+1]]=dp[i+1][idl[i+1]];
        for(int j=idl[i+1]-1;j>=0;j--)mx[1][j]=max(mx[1][j+1],dp[i+1][j]);//后缀最大值 

        dp[i][0]=max(mx[1][1],dp[i+1][0]);
        for(int j=1;j<=idl[i];j++){
            int add=0;
            if(lr[rid[i][j]][0]>1)add=max(add,mx[0][lr[rid[i][j]][0]-1]);
            if(lr[rid[i][j]][1]<idl[i+1])add=max(add,mx[1][lr[rid[i][j]][1]+1]);
            dp[i][j]=v[rid[i][j]]+max(add,dp[i+1][0]);
        }
    }
    cout<<max(dp[1][1],dp[1][0]);
    return 0;
}