题解：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;
}