• + 2 comments

    C++ Solution

    #include<cstdio>
    #include<ctime>
    #include<cstdlib>
    #include<vector>
    
    using namespace std;
    
    int INF, N, M, nr, V, v[400009], ap[200009], t[200009];
    bool scos[200009];
    vector<int> muchii[200009];
    
    struct nod{
        int K, P, nr;
        nod *l, *r, *t;
        nod (int K, int P, int nr, nod *l, nod *r){
            this->nr = nr;
            this->l = l;
            this->r = r;
            this->P = P;
            this->K = K;
            this->t = 0;
        }
    } *adresa1[200009], *adresa2[200009], *nil, *R;
    
    int Rand(){
        return ((rand() % 32768) << 15) + (rand() % 32768) + 1;
    }
    
    void reup(nod *&n){
        if(n->l != nil) n->l->t = n;
        if(n->r != nil) n->r->t = n;
        n->nr = n->l->nr + n->r->nr + 1;
    }
    
    void rot_left(nod *&n){
        nod *t = n->l;
        n->l = t->r, t->r = n;
        t->t = n->t;
        reup(n);
        reup(t);
        n = t;
    }
    
    void rot_right(nod *&n){
        nod *t = n->r;
        n->r = t->l, t->l = n;
        t->t = n->t;
        reup (n);
        reup (t);
        n = t;
    }
    
    void balance(nod *&n){
        if(n->l->P > n->P)
            rot_left(n);
        else if(n->r->P > n->P)
            rot_right(n);
    }
    
    void Insert(nod *&n, int Poz, int K, int P){
        if(n == nil){
            n = new nod(K, P, 1, nil, nil);
            return;
        }
        if(n->l->nr >= Poz) Insert (n->l, Poz, K, P);
        else Insert(n->r, Poz - n->l->nr - 1, K, P);
        reup (n);
        balance (n);
    }
    
    void Erase(nod *&n, int Poz){
        if(n->l->nr >= Poz)
            Erase(n->l, Poz);
        else if(n->l->nr + 1 < Poz)
            Erase(n->r, Poz - n->l->nr - 1);
        else{
            if(n->l == nil && n->r == nil){
                delete n;
                n = nil;
            }
            else{
                if(n->l->P > n->r->P)
                    rot_left (n);
                else
                    rot_right (n);
                Erase(n, Poz);
            }
        }
        if(n != nil) reup (n);
    }
    
    void join(nod *&R, nod *&Rl, nod *&Rr){
        R = new nod(0, 0, Rl->nr + Rr->nr + 1, Rl, Rr);
        Erase(R, Rl->nr + 1);
    }
    
    void split(nod *&R, nod *&Rl, nod *&Rr, int Poz){
        Insert (R, Poz, 0, INF);
        Rl = R->l, Rl->t = 0;
        Rr = R->r, Rr->t = 0;
        delete R, R = nil;
    }
    
    bool nu_radacina(nod *&n){
        if(n->t != 0 && (n->t->l == n || n->t->r == n)) return 1;
        return 0;
    }
    
    void det_root(nod *n, nod *&R){
        while(1){
            if (nu_radacina(n))
                n = n->t;
            else
                break;
        }
        R = n;
    }
    
    int Get_Pos(nod *n){
        int ans = n->l->nr + 1;
        while (1){
            if (nu_radacina(n)){
                if(n->t->l == n) n = n->t;
                else ans += n->t->l->nr + 1, n = n->t;
            }
            else break;
        }
        return ans;
    }
    
    void dfs(int nod){
        ap[nod] = 1;
        v[++nr] = nod;
        for(vector<int>::iterator it = muchii[nod].begin(); it != muchii[nod].end(); it++)
            if (ap[*it] == 0){
                dfs(*it);
                t[*it] = nod;
            }
        v[++nr] = -nod;
    }
    
    void build(nod *&n){
        if(n == nil) return ;
        if(n->K < 0)
            adresa2[-n->K] = n;
        else
            adresa1[n->K] = n;
        build(n->l);
        build(n->r);
    }
    
    void afis(nod *&n){
        if (n == nil) return ;
        afis(n->l);
        printf("%d ", n->K);
        afis(n->r);
    }
    
    void Del(int a, int b){
        if(t[b] == a){
            int aux = a;
            a = b;
            b = aux;
        }
        nod *R, *R1, *R2, *R3, *R4;
        det_root(adresa1[a], R);
        int p1, p2;
        p1 = Get_Pos(adresa1[a]);
        p2 = Get_Pos(adresa2[a]);
        split(R, R4, R3, p2);
        split(R4, R1, R2, p1 - 1);
        R2->t = 0;
        join(R, R1, R3);
    }
    
    int main(){
        srand(time(0));
        INF = (1 << 30) + 7;
        scanf("%d", &N);
        for(int i = 1; i < N; i++){
            int X, Y;
            scanf("%d %d", &X, &Y);
            muchii[X].push_back(Y);
            muchii[Y].push_back(X);
        }
        dfs(1);
        nil = new nod(0, 0, 0, 0, 0);
        R = nil;
        for(int i = 1; i <= nr; i++)
            Insert (R, i - 1, v[i], Rand());
        build(R);
        int V = 0;
        scanf("%d", &M);
        for(int i = 1; i <= M; i++){
            int x;
            scanf("%d", &x), x ^= V;
            nod *R;
            det_root(adresa1[x], R);
            printf("%d\n", R->nr / 2), scos[x] = 1, V = R->nr / 2;
            for(auto it = muchii[x].begin (); it != muchii[x].end (); it ++)
                if (!scos[*it]) Del(x, *it);
        }
        return 0;
    }