2021-2022 ACM-ICPC Brazil Subregional Programming Contest M.Monarchy in Vertigo 思维/模拟/图论入门

题目分析

题目大意：王位继承问题，要求确认每次人去世后的继承人编号。规则如下

• 遵循直系优先于旁系规则，也就是当支系的祖先去世后；
• 同一支系下，优先选择编号较小的孩子。

现在有两种操作：

1. o p = 1 , x i op = 1, x_i op=1,xi​，表示编号为 x i x_i xi​的节点下新增一个儿子；
2. o p = 1 , x i op = 1, x_i op=1,xi​，表示编号为 x i x_i xi​的节点删除(去世)。

思路分析：很容易发现题目要求我们找的就是按照 D F S DFS DFS序上删点后的首结点，那么我们只需要对所有的节点按照 d f s dfs dfs序进行排序，然后暴力加点删点即可。由于删除的点一定是队首的 d f s dfs dfs序较小的点，因此这里可以用 s e t set set或 q u e u e queue queue维护序列均可。

Accepted Code

#include 
using namespace std;

const int N = 1e6 + 5;
struct Node{
    int x, w;
    bool operator