is->fa = ff; f->push_up(); } inline Node*splay() { go(); while (!isroot()) { if (!fa->isroot()) d() == fa->d() ? fa->rot() : rot(); rot(); } push_up(); return this; } inline Node* access() {//access后this就是到根的一条splay，并且this已经是这个splay的根了 for (Node *p = this, *q = null; p != null; q = p, p = p->fa) { p->splay()->setc(q, 1); p->push_up(); } return splay(); } inline Node* find_root() { Node *x; for (x = access(); x->push_down(), x->ch[0] != null; x = x->ch[0]); return x; } void make_root() { access()->flip(); } void cut() {//把这个点的子树脱离出去 access(); ch[0]->fa = null; ch[0] = null; push_up(); } void cut(Node *x) { if (this == x || find_root() != x->find_root())return; else { x->make_root(); cut(); } } void link(Node *x) { if (find_root() == x->find_root())return; else { make_root(); fa = x; } } }; Node pool[N], *tail; Node *node[N]; void init(int n) { tail = pool; null = tail++; null->clear(0); for (int i = 1; i <= n; i++) { node[i] = tail++; node[i]->clear(i); } } void debug(Node *x) { if (x == null)return; x->put(); debug(x->ch[0]); debug(x->ch[1]); } int n, m, q; struct BST { int f[N]; void init(int n) { for (int i = 1; i <= n; i++)f[i] = i; } int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void Union(int u, int v) { u = find(u); v = find(v); if (u == v)return; if (u > v)swap(u, v); f[u] = v; } }cha; void insert(int x, int y) { // puts(**===); for (int i = 1; i <= max(x, y); i++)debug(node[i]), puts();puts(); if (cha.find(x) == cha.find(y)) { node[y]->access(); // puts(**); for (int i = 1; i <= max(x, y); i++)debug(node[i]), puts();puts(); int id = node[y]->min_id; if (y <= id)return; // printf(change id:%d , id); bit.change(id, -1); node[id]->val--; node[id]->cut(node[x]); } else cha.Union(x, y); // puts(---------);for (int i = 1; i <= x; i++)debug(node[i]), puts();puts(); bit.change(y, 1); node[y]->make_root(); node[y]->val++; node[y]->push_up(); node[y]->fa = node[x]; // puts(@@@@@@);for (int i = 1; i <= x; i++)debug(node[i]), puts();puts(); } int ans[N]; struct { struct Edge { int to, nex, id; }edge[N << 1]; int head[N], edgenum; void init(int n) { memset(head, -1, (10 + n) *sizeof(int)); edgenum = 0; } void add(int u, int v, int id = 0) { Edge E = { v, head[u], id}; edge[edgenum] = E; head[u] = edgenum++; } }E, Q; int main() { while (~scanf(%d%d%d, &n,&m,&q)) { E.init(n); Q.init(n); cha.init(n); for (int i = 0, u, v;i < m; i++) { rd(u), rd(v); if (u == v) {i--, m--;continue;} if (u < v)E.add(v, u);else E.add(u, v); } for (int i = 0, u, v;i < q; i++) { rd(u); rd(v); Q.add(v, u, i); } bit.init(n); init(n); for (int i = 1; i <= n; i++) { for (int j = E.head[i]; ~j; j = E.edge[j].nex) insert(i, E.edge[j].to); for (int j = Q.head[i]; ~j; j = Q.edge[j].nex) ans[Q.edge[j].id] = n - bit.query(Q.edge[j].to, i); } for (int i = 0; i < q; i++) pt(ans[i]), puts(); } return 0; } /* 7 9 1 1 2 1 3 1 5 1 6 4 7 4 6 2 7 6 2 4 3 2 7 ans:3 */
?
?
|