#include<bits/stdc++.h>
using namespace std;
int n,m,k,p,x,mark[100005]={0};
list<int>l; //链表 
list<int>::iterator it[100005],tmpit; //iterator迭代器 
//it 存每个数据的地址 
int main()
{ cin>>n;
l.push_back(1);
it[1]=l.begin(); //将1元素的地址存入it中 
for(int i=2;i<=n;i++)
{
     cin>>k>>p;
     if(p==0)
     {
        it[i]=l.insert(it[k],i);  //将i插入k地址的左边 ，并且it[i]是i的地址 
     }
     else   //将k插入i的右边 
     {
        if(it[k]==l.end()) //如果元素k是链表中最后一个元素  
         {
            l.push_back(i);  //将i插入链表最后面，，也就是k的右边 
            it[i]=l.end(); //i地址就是链表尾部 
          }
          else
          {
            tmpit=it[k];  //tmpit是k的地址 
            tmpit++;    //地址++ 
            it[i]=l.insert(tmpit,i); //将i插入k的右边 也就是插入k++的前面 
          }
     }
}cin>>m;
for(int i=1;i<=m;i++)
 {
    cin>>x;
    if(mark[x]==1) continue;
    mark[x]=1;
    l.erase(it[x]);  //删除x（找到x的地址，删除） 
 }
 for(tmpit=l.begin();tmpit!=l.end();tmpit++) //地址迭代器 
   {
    cout<<*tmpit<<" ";//用* 
   }
    return 0;
}

结构体双向链表

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct node {
    int left;      // 左 
    int right;     //右 
} que[100001];
int head = 1;
int main() {
    int n;
    scanf("%d",&n);
    for(int i = 2; i<=n; i++) {
        int t1,t2;
        scanf("%d%d",&t1,&t2);
        if(t2==1)   //将i插入到t1的右边 
        {                                   //此时 t1 i ** 
            que[i].right = que[t1].right;   //i的右边是t1的右边的数字（链表） 
            que[t1].right = i;             //t1的右边是i 
            que[i].left = t1;               //i的左边是t1 
            que[que[i].right].left = i;     //下一个数据的左边是i 
        } 
        else //将i插入 t1的左边 
         {                                   //此时 i t1  ** 
            que[i].left = que[t1].left;      //i的左边是t1之前的左边 
            que[t1].left = i;                // t1的左边是i 
            que[i].right = t1;               //i的右边是t1 
            que[que[i].left].right = i;      //   上一个数据的右边是i 
            if(t1 == head)               //此位置 的左边已经插入数据了
                                        // 如果此位置是头 ，那么头部需要更新 
            {
                head = i;            //头节点 
            }
        }
    }
    int m;                      //删除 
    scanf("%d",&m);
    for(int i = 1; i<=m; i++) {
        int tmp;
        scanf("%d",&tmp);                           //删除tmp 
        que[que[tmp].left].right = que[tmp].right; //tmp左边数据的左边变成tmp的右边 
        que[que[tmp].right].left = que[tmp].left;//tmp右边数据的左边变成tmp的左边 
        que[tmp].left = que[tmp].right = 0;//tmp的左边变成，右边变成0 
    }
    printf("%d",head);    //输出头结点 
    int tmp = head;         //头结点位置 
    while(que[tmp].right){   //不为0 
        tmp = que[tmp].right;     //输出头部的右边 
        printf(" %d",tmp);
    }
    return 0;
}