C++14(g++5.4) 解法, 执行用时: 5ms, 内存消耗: 1396K, 提交时间: 2020-04-17 11:08:31

#include <iostream>
#include <cstring>
#include <map>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e5+10;
ll depth[maxn];
ll head[maxn];
ll w[maxn];
struct Edge{
	ll next,to;
}e[maxn<<1];
ll cnt;
ll ans=-100;
ll ding[maxn];
void add(ll x,ll y){
	e[cnt].to=y;
	e[cnt].next=head[x];
	head[x]=cnt++;
}

bool cmp(ll a,ll b){
	return ding[a]+w[b]>ding[b]+w[a];
}

void dfs(ll u,ll fa,ll de){
	vector<int> son;
	for(int i=head[u];~i;i=e[i].next){
		int v=e[i].to;
		if(v==fa) continue;
		dfs(v,u,de+1);
		son.push_back(v);
	}
	if(son.size()==0) {
		ding[u]=w[u];
		return ;
	}
	ll sum=0;
	sort(son.begin(),son.end(),cmp);
	//
	for(int i=0;i<son.size();i++){
		int v=son[i];
		ding[u]=max(ding[u],sum+ding[v]);
		sum+=w[v];
	}
	ding[u]=max(ding[u],sum+w[u]);
	
}

int main()
{
	for(int i=0;i<maxn;i++) head[i]=-1;
	ll n;
	cin>>n;
	for(int i=0;i<n-1;i++){
		ll p;
		cin>>p;
		add(i+1,p);
		add(p,i+1);
	}
	for(int i=0;i<n;i++){
		cin>>w[i];
	}
	dfs(0,-1,0);
	//cout<<"ok"<<endl;
	ll ans=0;
	cout<<ding[0]<<endl; 
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 7ms, 内存消耗: 2808K, 提交时间: 2020-08-21 17:30:43

#include<bits/stdc++.h>
const int maxn=100010; 
int n;
int MU[maxn],ans[maxn];
std::vector<int>son[maxn];
void dfs(const int u);
bool cmp(const int &_a, const int &_b);
int main() {
  scanf("%d", &n);
  for (int i = 2, x; i <= n; ++i) {
    scanf("%d", &x);
      ++x;
    son[x].push_back(i);
  }
  for (int i = 1; i <= n; ++i) {
    scanf("%d", MU + i);
  }
  dfs(1);
  printf("%d\n",ans[1]);
  return 0;
} 
void dfs(const int u) {
  for (auto v : son[u]) {
    dfs(v);
  }
  std::sort(son[u].begin(), son[u].end(), cmp);
  int _ret = 0;
  for (auto v : son[u]) {
    if (_ret >= ans[v]) {
      _ret -= MU[v];
    } else {
      ans[u] += ans[v] - _ret;
      _ret = ans[v] - MU[v];
    }
  }
  ans[u] += std::max(0, MU[u] - _ret);
}
inline bool cmp(const int &_a, const int &_b) {
  return (ans[_a] - MU[_a]) > (ans[_b] - MU[_b]);
}

C++(g++ 7.5.0) 解法, 执行用时: 4ms, 内存消耗: 656K, 提交时间: 2023-07-18 17:17:28

#include<bits/stdc++.h>

#define x first
#define y second
using namespace std;
using i128=__int128;
typedef unsigned long long ULL;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1010;
vector<int> e[N];
int w[N];
int n;
bool cmp(PII p1,PII p2){
    return p1.x-p1.y>p2.x-p2.y;
}

int dfs(int u){
    vector<PII> sw;
    for(auto v:e[u]){
        sw.push_back({dfs(v),w[v]});
    }
    int maxs=0,val=0;
    sort(sw.begin(),sw.end(),cmp);
    for(auto sval:sw){
        maxs=max(maxs,val+sval.x);
        val+=sval.y;
    }
    return max(val+w[u],maxs);
}

void solve(){
    cin >>n;
    for(int i=1;i<n;i++){
        int v;
        cin >>v;
        e[v].push_back(i);
    }
    for(int i=0;i<n;i++)   cin>>w[i];
    cout <<dfs(0) <<"\n";
}

int main(){
    int t=1;
    //cin >>t;
    while(t--)  solve();
    return 0;
}