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

原题链接

• 洛谷 P12652 [KOI 2024 Round 2] 拔树游戏

解题思路

拔除操作可抽象为以下过程：

1. 每步输出当前根节点的权值；
2. 移除根节点，并将其所有子节点加入候选集合；
3. 从候选集合中选取权值最小的节点作为新根，继续执行。

设当前根为 $u$。特殊路径的下一步必然进入 $u$ 的权值最小子节点 $v$，并在操作后将 $v$ 提升为新根。同时，$u$ 的其他子节点在后续某一步可能成为根，因此也应进入候选集合。由此得到递推过程：

1. 初始时，根节点 $1$ 为唯一候选；
2. 每次取出候选集合的最小元素并输出；
3. 将该节点的所有子节点加入集合；
4. 重复直至集合为空。

由于权值互不相同，集合最小值始终与下一步特殊路径的根节点一致，该过程与题目定义完全等价。

使用优先队列维护候选集合，每个节点仅入队和出队各一次，时间复杂度为 $O(n \log n)$。

参考代码

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

using ll=long long;
const int N=300005;
int a[N];
vector<int> G[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	for(int i=2;i<=n;i++)
	{
		int u;
		cin>>u;
		G[u].push_back(i);
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	priority_queue<pair<int,int>> q;
	q.push({-a[1],1});
	while(!q.empty())
	{
		auto [w,u]=q.top();
		q.pop();
		cout<<-w<<'\n';
		for(auto v:G[u])q.push({-a[v],v});
	}
	return 0;
}