wa on #7求助
查看原帖
wa on #7求助
736900
lishitang楼主2024/10/1 19:53
#include<iostream>
#include<vector>
#include<cmath>

using namespace std;

const int N=5e3+10;

int n,a[N],len,f[N],dp[N];
vector <int >v[N];

int dfs(int x){
	int ans=0;
	for(int i=0;i<v[x].size();i++){
		if(!f[v[x][i]])f[v[x][i]]=dfs(v[x][i]);
		ans+=f[v[x][i]];
	}
	return ans+1;
}

int main(){
	cin>>n;
	for(int i=2;i<=n;i++){
		int x;cin>>x;
		v[x].push_back(i);
	}
	f[1]=dfs(1);
	int ans=0;
	for(int k=1;k<=n;k++){
		for(int i=0;i<v[k].size();i++)a[i+1]=f[v[k][i]];
		int V=ceil(1.0*(f[k]-1)/2);
		for(int i=0;i<=V;i++)dp[i]=0;
		for(int i=1;i<=v[k].size()+1;i++)
			for(int j=V;j>=a[i];j--)
				dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
		ans+=(dp[V]*(f[k]-1-dp[V]));
	} 
	cout<<ans<<endl;
	return 0;
}
2024/10/1 19:53
加载中...