You are viewing a single comment's thread. Return to all 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; }
Seems like cookies are disabled on this browser, please enable them to open this website
Tree Splitting
You are viewing a single comment's thread. Return to all comments →
C++ Solution