自动搬运

查看原文

来自洛谷，原作者为

	bluewindde d2673e765642345244b4fb8edf1add1cf8425a4b7743f39b020d410d67ce15b0

搬运于2025-08-24 22:34:21，当前版本为作者最后更新于2023-08-01 14:47:38，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

upd 2023.8.1：修改了题解的表述错误。

解法

首先，用一个正常人的思维，我们只应该在能赚的前提下进入一颗子树，所以需要先预处理出进入以节点 $i$ 为根节点的子树的进入的需求 $need_i$。然后再用 bfs 统计答案。

预处理

那么应该怎么处理子树的进入需求呢？

我们可以使用 dfs，在回溯时处理需求。这里有两种情况：

• 节点 $u$ 不是鸟巢，即 $a_u\ge0$，此时不需要进入需求，$need_u=0$。
• 节点 $u$ 是鸟巢，即 $a_u<0$。
  此时把节点 $u$ 的子节点加入优先队列，记录当前总的收入 $tot$。
  每次循环取出优先队列中 $need_v$ 最小的节点 $v$。
  若 $tot-need_u\ge0$，意味着搜索到可以赚的点，此时退出循环；
  若 $tot<need_v$，意味着当前的收入不足以进入节点 $v$，则使 $tot\gets need_v$。
  在循环结束时，将 $tot$ 加上节点 $v$ 的权值 $a_v$，并把节点 $v$ 的所有子节点加入优先队列。
  退出循环后，一定要再判断一次是否满足 $tot-need_u\ge0$。如果没有搜索到可以赚的点，意味着无论如何都会亏，所以不走这棵子树，将 $need_u\gets\inf$。

统计答案

用 bfs 统计，先向优先队列内推入根节点，令 $ans\gets s$，每次取出优先队列中 $need_v$ 最小的节点 $v$。若 $ans<need_v$，则退出循环。否则将 $ans$ 加上 $a_v$，并把 $v$ 的子节点推入优先队列。

更多的内容可以看代码注释。

AC 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct node {
	int need,index;
	inline node(int n,int i):need(n),index(i) {}
	inline bool operator<(const node &b) const { // 重载比较函数 记得加 const
		return need>b.need;
	}
};
priority_queue<node> to_vis;

int n,s;
int fa[6005],a[6005],need[6005];
vector<int> child[6005];

inline void clear() {
	while(!to_vis.empty()) {
		to_vis.pop();
	}
}

inline void dfs(int u) {
	clear();
	for(auto i:child[u]) { // 优先处理子节点
		dfs(i);
	}
	if(a[u]>=0) { // 没有鸟巢，所以进入条件为0
		need[u]=0;
		return ;
	}
	clear();
	for(auto i:child[u]) {
		to_vis.push(node(need[i],i));
	}
	need[u]-=a[u]; // 要给这个节点上的鸟的苹果的数量
	bool flag=false;
	int tot=0;
	while(!to_vis.empty()) {
		if(tot-need[u]>=0) { // 搜索到可以赚的点，退出
			flag=true;
			break;
		}
		node x=to_vis.top();
		to_vis.pop();
		if(tot<need[x.index]) {
			need[u]+=need[x.index]-tot; // 排除这个点，继续尝试
			tot=need[x.index];
		}
		tot+=a[x.index]; // 向子树加入新的点
		for(auto i:child[x.index]) { // 并且把这个点的子节点加进队列
			to_vis.push(node(need[i],i));
		}
	}
	if(tot-need[u]>=0) { // 搜索到可以赚的点，退出
		flag=true;
	}
	if(!flag) {
		need[u]=1e18; // 无论如何都会亏，所以不走这棵子树
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>s;
	for(int i=2;i<=n;++i) {
		cin>>fa[i];
		child[fa[i]].push_back(i);
	}
	for(int i=1;i<=n;++i) {
		cin>>a[i];
	}
	dfs(1);
	clear();
	to_vis.push(node(need[1],1));
	int ans=s;
	while(!to_vis.empty()) {
		node x=to_vis.top();
		to_vis.pop();
		if(ans<need[x.index]) { // 没有达到任何一棵子树可以进入的要求，退出
			break;
		}
		ans+=a[x.index];
		for(auto v:child[x.index]) {
			to_vis.push(node(need[v],v));
		}
	}
	cout<<ans;
	return 0;
}

注意事项

如果用 auto 关键字遍历列表，一定要记得选 -std=c++14 或者更高。

优先队列不能用 clear 方法清空，需要手写循环来清空。

开 long long！！！