C++(clang++ 11.0.1) 解法, 执行用时: 86ms, 内存消耗: 34076K, 提交时间: 2023-01-07 12:17:47

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const int mod =100000007;
ll a[N],dp[N],g[N],n;
vector<int>ve[N];
void dfs(int x){
	for(auto i:ve[x]){
		dfs(i);
		dp[x]=max(dp[x],dp[i]);
		g[x]+=g[i];
	}
	dp[x]=a[x]+max(dp[x],(g[x]+1)/2);
	g[x]+=a[x];
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=2;i<=n;i++){
		int k;
		cin>>k;
		ve[k].push_back(i);
	}
	dfs(1);
	cout<<dp[1]<<endl;
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 74ms, 内存消耗: 35776K, 提交时间: 2023-01-06 21:25:22

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll i,j,k,n,m,t,a[1005000],res,f[1005000],g[1005000];
vector<int> v[1005000];

void dfs(int x){
	for(auto i:v[x]){
		dfs(i);
		f[x]=max(f[x],f[i]);
		g[x]+=g[i];
	}
	f[x]=a[x]+max(f[x],(g[x]+1)/2);
	g[x]+=a[x];
}

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
	for(i=2;i<=n;i++){
		cin>>k;v[k].push_back(i);
	}
	dfs(1);
	cout<<f[1];
}