P1160 题解

BSJT_303 · 2025-03-01 14:16:34 · 题解

#include <iostream>
using namespace std;

struct Node {
    int id;
    Node* pre;
    Node* nxt;
    Node(int num): id(num), pre(nullptr), nxt(nullptr) {}
};

void insL(Node* t, Node* n) {
    n->pre = t->pre;
    n->nxt = t;
    if (t->pre) t->pre->nxt = n;
    t->pre = n;
}

void insR(Node* t, Node* n) {
    n->nxt = t->nxt;
    n->pre = t;
    if (t->nxt) t->nxt->pre = n;
    t->nxt = n;
}

void rem(Node* n) {
    if (n->pre) n->pre->nxt = n->nxt;
    if (n->nxt) n->nxt->pre = n->pre;
    delete n;
}

int main() {
    int N, M, k, p, x;
    cin >> N;
    Node* h = new Node(1);
    Node* nd[100005] = {nullptr};
    nd[1] = h;
    for (int i = 2; i <= N; i++) {
        cin >> k >> p;
        Node* n = new Node(i);
        nd[i] = n;
        if (p == 0) insL(nd[k], n);
        else insR(nd[k], n);
    }
    cin >> M;
    for (int i = 0; i < M; i++) {
        cin >> x;
        if (nd[x]) {
            rem(nd[x]);
            nd[x] = nullptr;
        }
    }
    Node* cur = h;
    while (cur->pre) cur = cur->pre;
    bool fst = true;
    while (cur) {
        if (!fst) cout << " ";
        cout << cur->id;
        fst = false;
        cur = cur->nxt;
    }
    cout << endl;
    return 0;
}