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

· · 题解

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;
}