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

· · 题解

不懂为什么题解区都写的这么复杂。来一种思路和代码都很清新的做法。

solution

感觉这玩意在树上 dp 是不好设计状态的，考虑把树当成序列来做。

具体的，一个自然的思路是按照深度 dp。我们设 f_{i} 表示从根往下，已经考虑到节点 i 的最大值。

转移是简单的，可以从深度为 1 \sim dep_{i}-1 的任何一个点转移过来，除了父亲。

即 f_{i}=\max\limits_{j\neq fa_{i}}\{f_{j}\}。

那么维护一个全局最大值和全局次大值即可，复杂度 O(n)。

代码不到 800B。

code

#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define pb push_back
int n,m,i,j,ans,x,mxd,v[N],f[N];
int mx,cmx,val[N],dep[N],fa[N];
std::vector<int>G[N],pt[N];
void dfs(int x,int k){
    dep[x]=dep[k]+1,mxd=max(mxd,dep[x]);
    pt[dep[x]].pb(x),fa[x]=k;
    for(int y:G[x]){
        if(y==k) continue;
        dfs(y,x);
    }
}
int main(){
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        scanf("%d",&x);
        G[i].pb(x),G[x].pb(i);
    }
    for(i=1;i<=n;i++) scanf("%d",&v[i]);
    dfs(1,0),f[1]=v[1],mx=v[1];
    for(i=2;i<=mxd;i++){
        for(int k:pt[i]){
            if(f[fa[k]]==mx) f[k]=cmx+v[k];
            else f[k]=mx+v[k];
        }
        for(int k:pt[i]){
            if(f[k]>mx) cmx=mx,mx=f[k];
            else if(f[k]>cmx) cmx=f[k];
        }  
    }
    for(i=1;i<=n;i++) ans=max(ans,f[i]);
    printf("%d\n",ans);
    return 0;
}