自动搬运

查看原文

来自洛谷，原作者为

	chenxi797 壶关条件见主页，私||关我可得2小号回关，私||初三蒟蒻||ENTP||天秤座

搬运于2025-08-24 23:17:08，当前版本为作者最后更新于2025-08-08 09:17:48，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P12652 [KOI 2024 Round 2] 拔树游戏 题解

题意

定义拔除操作：将根结点删除，空缺的位置由权值最小的子结点上移填充，以此类推直到叶子结点。

我们需要重复执行拔除操作直到树空。输出每次进行操作之前，根结点的权值。

思路

这种不断将小的数向上顶的过程，我们可以用堆来实现。

我们可以选择直接将选出的子结点的所有儿子都直接加入到我们的堆里，有堆就可以保证堆顶的结点权值最小。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int n,m;
int a[N]; // 权值
vector <int> s[N]; // 每个节点的儿子节点的编号
priority_queue <pair<int,int>> ans; // 小根堆存点权，编号
signed main()
{
	int n,m;
	cin >> n;
	for (int i = 2;i <= n;i++)
	{
		int x;
		cin >> x;
		s[x].push_back(i);
	}
	for (int i = 1;i <= n;i++) cin >> a[i];
	ans.push(make_pair(-a[1],1)); // 存入最初根节点
	while (n--)
	{
		cout << -ans.top().first << endl; // 每次操作之前先输出根节点的权值
		int x = ans.top().second; // 记录下根节点的编号，之后弹出
		ans.pop();
		for (int i = 0;i < s[x].size();i++)
		{
			int v = s[x][i];
			ans.push(make_pair(-a[v],v)); // 把所有儿子节点存入小根堆
		}
	}
	return 0;
}