传送门
思路
这道题就是一道链表模板题，还是有些巧妙的啦
因为有频繁的插入和删除操作，正好可以用链表做，这里用的是数组模拟的双向链表
首先定义结构体，表示链表的节点，(a[x].l)表示(x)的左边这个同学的编号，(a[x].r)表示(x)的右边同学的编号
struct node {
int l, r;
} a[N];
下面有几个重点操作，分别是左边插入，右边插入，删除操作，以及输出
（可能有些绕口，见谅见谅）
1.左边插入
两个参数表示：将(x)插入到(pos)节点的左边（因为是左边插入嘛）
因为我们把(x)插入到了(pos)的左边，所以(x)的右边节点自然应该为(pos)节点，即(a[x].l=a[pos].r)而(x)的左边节点则为原来(pos)节点的左边节点，即(a[x].l = a[pos].l)，这时原本(pos)的左边节点的右边节点就变为了(x)，即(a[a[pos].l].r=x)，最后(pos)节点的左边节点变为了(x)，即(a[pos].l=x)，当然顺序是要有的，写错了就可能导致答案错误
inline void addleft(int x, int pos) {
a[x].r = pos;
a[a[pos].l].r = x;
a[x].l = a[pos].l;
a[pos].l = x;
}
2.右边插入
右边插入与左边插入完全相反，这里自己体会
inline void addright(int x, int pos) {
a[x].l = pos;
a[a[pos].r].l = x;
a[x].r = a[pos].r;
a[pos].r = x;
}
3.删除操作
那么如何删除这个节点呢？？
我们可以一开始把所有节点的左右节点都定义为(-1)，表示没有左右节点，而在插入之后就有了左右节点
我们把当前节点(pos)的左边节点的右边节点设置成(a[pos].r)，即(a[a[pos].l].r = a[pos].r)，把其右边节点的左边节点设置为(a[pos].l)，即(a[a[pos].r].l = a[pos].l)，然后删除操作就完成了一半，在遍历时就会直接跳过这个节点，然后把(pos)节点的左右节点都设置为(-1)，然后就完成了删除操作
inline void dele(int x) {
if(a[x].l == -1) return;
a[a[x].l].r = a[x].r;
a[a[x].r].l = a[x].l;
a[x].l = -1;
a[x].r = -1;
}
4.输出
那么如何输出呢？
我们在一开始把(0)节点的右边节点设为(1),(1)节点的左边节点设为(0)，然后在过程中这些节点的左右节点都发生了变化，但是第一个节点一定是(0)号节点的右边节点，然后循环定义(x)为(x)节点的右边节点，如果不为(-1)就一直输出，这样就完成了输出操作
inline void write() {
int x = a[0].r;
while(1) {
cout << x << ' ';
if(a[x].r == -1) break;
x = a[x].r;
}
}
代码
#include <bits/stdc++.h>
#define N 1000111
using namespace std;
struct node {
int l, r;
} a[N];
int n, m;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(; isdigit(c); c = getchar()) x = x * 10 + c - 48;
return x * f;
}
inline void addright(int x, int pos) {
a[x].l = pos;
a[a[pos].r].l = x;
a[x].r = a[pos].r;
a[pos].r = x;
}
inline void addleft(int x, int pos) {
a[x].r = pos;
a[a[pos].l].r = x;
a[x].l = a[pos].l;
a[pos].l = x;
}
inline void dele(int x) {
if(a[x].l == -1) return;
a[a[x].l].r = a[x].r;
a[a[x].r].l = a[x].l;
a[x].l = -1;
a[x].r = -1;
}
inline void write() {
int x = a[0].r;
while(1) {
cout << x << ' ';
if(a[x].r == -1) break;
x = a[x].r;
}
}
int main() {
n = read();
int k, p;
for(int i = 1; i <= n; i++) {
a[i].l = a[i].r = -1;
}
a[1].l = 0;
a[0].r = 1;
for(int i = 2; i <= n; i++) {
k = read(), p = read();
if(p == 0) addleft(i, k);
else addright(i, k);
}
m = read();
for(int i = 1; i <= m; i++) {
k = read();
dele(k);
}
write();
return 0;
}