求hack
查看原帖
求hack
368675
wuruiheng楼主2024/9/28 17:59
#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> G[6005];
struct node{
	int id,dp,sz;
	bool operator < (const node &rhs) const{
		return dp<rhs.dp;
	}
}a[6005];
struct node2{
	int id,sz;
	bool operator < (const node2 &rhs) const{
		return sz<rhs.sz;
	}
};
void dfs(int u){
	a[u].dp=a[u].sz;
	for(int i=0;i<G[u].size();i++){
		dfs(G[u][i]);
		if(a[G[u][i]].sz>=0)a[u].dp+=a[G[u][i]].sz;
	}
	return;
}
signed main(){
	//freopen("test.in","r",stdin);
	//freopen("ans.out","w",stdout);
	int n,s;
	scanf("%lld%lld",&n,&s);
	for(int i=2;i<=n;i++){
		int p;
		scanf("%lld",&p);
		G[p].push_back(i);
	} 
	for(int i=1;i<=n;i++){
		 scanf("%lld",&a[i].sz); 
		 a[i].id=i;
	}
	G[0].push_back(1);
	dfs(0);
	priority_queue<node> q;
	priority_queue<node2> q2;
	int ans=0,sum=s;
	q.push({0,a[0].dp,0});
	while(!q.empty()){
		node now=q.top();
		q.pop();
		sum+=now.sz;
		while(!q2.empty()&&q2.top().sz+sum>=0){
			q.push(a[q2.top().id]);
			q2.pop();
		}
		if(sum<0) break;
		ans=max(ans,sum);
		for(int i=0;i<G[now.id].size();i++){
			if(a[G[now.id][i]].sz+sum>=0){
				q.push(a[G[now.id][i]]);
			}
			else{
				q2.push({G[now.id][i],a[G[now.id][i]].sz});	
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}
/*7 0
1 1 2 2 3 4
1 -1 -2 -5 2 5 10*/
2024/9/28 17:59
加载中...