自动搬运

查看原文

来自洛谷，原作者为

	esolreven **

搬运于2025-08-24 23:15:07，当前版本为作者最后更新于2025-05-04 21:11:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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;
}