数据结构、链表

由于序列内部元素不重，使用 list 维护序列，使用 unordered_map 记录每个编号对应的迭代器可以将插入操作和删除操作的时间复杂度优化至 $O(1)$。

时间复杂度 $O(n)$。

#include<bits/stdc++.h>
using namespace std;
unordered_map<int,list<int>::iterator> m;
list<int> s;
int n,k;
int main(){
    scanf("%d",&n);
    s.push_back(1),m[1]=s.begin();
    for(int i=2;i<=n;i++){
        static int x,y;
        scanf("%d%d",&x,&y);
        auto it=y ? next(m[x]):m[x];
        m[i]=s.insert(it,i);
    }
    scanf("%d",&k);
    for(int i=1;i<=k;i++){
        static int x;
        scanf("%d",&x);
        if(m.count(x)) s.erase(m[x]),m.erase(x);
    }
    for(auto i:s) printf("%d ",i);
    return 0;
}