原文发表于2018-04-15 08:15:09，我的luogu博客qwq。
看到题以后，要求维护一个可在任意位置修改添加删除元素的序列，那么显然我们可以用到链表。
然而本蒟蒻不久前刚刚学会链表。链表也是线性结构，和数组比较，它的物理内存不连续，逻辑内存连续。数组在任意位置插入删除元素效率极差，链表就很棒了。
下面是给和我一样蒟的老哥们。
链表通常用结构体存储，一个节点有三个值，前驱、后继、权值。
链表初始化
1 int init() 2 { 3 tot=2; 4 head=1;tail=2; 5 node[head].next=tail; 6 node[tail].pre=head; 7 }
在p后插入新节点 注意是在后
1 void insert(int p,int r)//插在p的后面 2 { 3 q=++tot; 4 node[q].val=r; 5 node[node[p].next].pre=q; 6 node[q].next=node[p].next; 7 node[p].next=q; 8 node[q].pre=p; 9 }
删除一节点
1 void remove(int p) 2 { 3 node[node[p].pre].next=node[p].next; 4 node[node[p].next].pre=node[p].pre; 5 }
这些是链表的基本操作。
这道题需要有一些变动。
由于每个人按号依次进入，所以val值就是本身的序号。
由于可以向左插也可以向右插，写这句的时候要有一些改动。向右直接插，向左需要向 向左插的节点的前驱插。
最后输出尤为注意。不能输出权值！具体见代码。
code
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 using namespace std; 5 int n,m,q,tmp,rp; 6 int tot=1; 7 int head; 8 bool b[100002]; 9 struct linkb{ 10 int val; 11 int pre,next; 12 }node[100002]; 13 void insert(int p,int r)//插在p的后面 14 { 15 q=++tot; 16 node[q].val=r; 17 node[node[p].next].pre=q; 18 node[q].next=node[p].next; 19 node[p].next=q; 20 node[q].pre=p; 21 } 22 void remove(int p) 23 { 24 node[node[p].pre].next=node[p].next; 25 node[node[p].next].pre=node[p].pre; 26 } 27 int main() 28 { 29 b[1]=1;node[1].val=1; 30 node[0].next=1; 31 scanf("%d",&n); 32 for(int i=2;i<=n;i++) 33 { 34 int x=0,y=0; 35 scanf("%d%d",&x,&y); 36 b[i]=1; 37 if(y==1) 38 { 39 insert(x,i); 40 } 41 else if(y==0) 42 { 43 insert(node[x].pre,i); 44 } 45 } 46 scanf("%d",&m); 47 for(int i=1;i<=m;i++) 48 { 49 int x=0; 50 scanf("%d",&x); 51 if(b[x]==0) continue; 52 b[x]=0; 53 rp++; 54 remove(x); 55 } 56 head=node[0].next; 57 //printf("%d ",node[head].val); 58 tmp=head; 59 for(int i=1;i<=n-rp;i++) 60 { 61 printf("%d ",node[tmp].val); 62 tmp=node[tmp].next; 63 } 64 printf(" "); 65 return 0; 66 }