如果要讲双链表的写法,那么不得不提y总在算基课里讲解的双链表模板,当然我个人不喜欢这个词

模板如下:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int h[N],e[N],l[N],r[N],idx = 2; 
void I(int a,int b)
{
    e[idx]=b;r[idx]=r[a];l[idx]=a;l[r[a]]=idx;r[a]=idx++;
}
void D(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}
int main()
{
    int m,a,b;cin >> m;
    string s;
    l[1]=0;r[0]=1;
    while(m--) {
        cin >> s;
        if(s=="R"){
            cin >> a;
            I(l[1],a);
        }
        if(s=="L") {
            cin >> a;
            I(0,a);
        }
        if(s=="D"){
            cin >> a;
            D(a+1);//偏移量 
        }
        if(s=="IL"){
            cin >> a >> b;
            I(l[a+1],b);
        }
        if(s=="IR") {
            cin >> a >> b;
            I(a+1,b);
        }
    }
    for(int i = r[0] ; i != 1 ; i = r[i]) 
        cout << e[i] << " ";
    return 0;
}

我相信没有人会画完图之后还不懂的~
那么对于洛谷这道题的解法就很明显了,直接套

直接套模板的ac代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int st[N],l[N],r[N],e[N],idx=2;
void I(int a,int b)
{
    e[idx]=b;r[idx]=r[a];l[r[a]]=idx;l[idx]=a;r[a]=idx++;
}
int main()
{
    int n,m,a,b;cin >> n;
    l[1]=0;r[0]=1;
    I(0,1);
    for(int i = 2 ; i <= n ; i++) { 
        cin >> a >> b;
        if(b==1) I(a+1,i);
        else I(l[a+1],i);
    }
    cin >> m; 
    for(int i = 1 ; i <= m ; i++) {cin >> a;st[a] = 1;} 
    for(int i = r[0];i!=1 ; i =r[i]) {
        int j = e[i];
        if(!st[j]) cout << j << " ";
    }
    return 0;
}

是不是很短吖~

接下来我们用第二种方法:STL大法
不过这个代码很蓟县,500~600ms过去的,差点超时,幸好洛谷这题数据水[手动狗头];

STL版本ac代码如下

#include <bits/stdc++.h>
using namespace std;
vector<int> v;
int st[100010];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n,a,b,m;cin >> n;
    v.push_back(1); 
    for(int i = 2 ; i <= n ; i++) {
        cin >> a >> b;
        auto t = find(v.begin(),v.end(),a);
        if(b==0) 
            v.insert(t,i);
        else 
            v.insert(t+1,i);
    }
    cin >> m;
    for(int i = 1 ; i <= m ; i++) {
        cin >> a;
        if(st[a]) continue;
        st[a]=1;/*
        auto t = find(v.begin(),v.end(),a);
        if(t!=v.end()) 
            v.erase(t);*/
    }
    for(int x : v) {
        if(!st[x]) cout << x << " ";
    }
    cout << endl;
    return 0;
}