由于没有看到图在任意时刻都是连通的..这一条件..于是只好打了动态树..
#include
using namespace std;
typedef long long LL;
const int maxn = 30005;
const int maxm = 400005;
struct Node *null;
struct Node
{
Node *fa, *ch[2];
int sum, val, lazy, rev;
inline void push_up()
{
sum = ch[0]->sum + ch[1]->sum + val;
}
inline void setc(Node *p, int d)
{
ch[d] = p;
p->fa = this;
}
inline bool d() {
return fa->ch[1] == this;
}
inline bool isroot()
{
return fa == null || fa->ch[0] != this && fa->ch[1] != this;
}
inline void flip()
{
if(this == null)return;
swap(ch[0], ch[1]);
rev ^= 1;
}
inline void update()
{
if(this == null) return;
val = sum = 0;
lazy = 1;
}
inline void push_down()
{
if(rev) {
ch[0]->flip(), ch[1]->flip(), rev = 0;
}
if(lazy) {
ch[0]->update();
ch[1]->update();
lazy = 0;
}
}
inline void go()
{
if(!isroot()) fa->go();
push_down();
}
inline void rot() {
Node *f = fa, *ff = fa->fa;
int c = d(), cc = fa->d();
f->setc(ch[!c], c);
this->setc(f, !c);
if(ff->ch[cc] == f) ff->setc(this, cc);
else this->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() {
for(Node *p = this, *q = null; p != null; q = p, p = p->fa) {
p->splay()->setc(q, 1);
p->push_up();
}
return splay();
}
void make_root() {
access()->flip();
}
void link(Node *x) {
make_root();
fa = x;
}
}pool[maxm], *tail, *node[maxn];
Node *newnode(int val)
{
tail->val = tail->sum = val;
tail->rev = tail->lazy = 0;
tail->fa = tail->ch[0] = tail->ch[1] = null;
return tail++;
}
void init()
{
tail = pool;
null = tail++;
null->val = null->sum = 0;
null->rev = null->lazy = 0;
null->fa = null->ch[0] = null->ch[1] = null;
}
struct ope
{
int kk, u, v;
ope(int kk = 0, int u = 0, int v = 0) : kk(kk), u(u), v(v) {}
}op[maxm];
multiset edge[maxn];
multiset::iterator it;
int ans[maxm];
int f[maxn];
int find(int u)
{
return f[u] = u == f[u] ? f[u] : find(f[u]);
}
void merge(int a, int b)
{
int aa = find(a), bb = find(b);
f[aa] = bb;
}
void update(Node *x, Node *y)
{
x->access();
for(x = null; y != null; x = y, y = y->fa) {
y->splay();
if(y->fa == null) {
y->ch[1]->update();
x->update();
y->val = 0;
y->push_up();
return;
}
y->setc(x, 1);
y->push_up();
}
}
int ask(Node *x, Node *y)
{
x->access();
for(x = null; y != null; x = y, y = y->fa) {
y->splay();
if(y->fa == null)
return y->val + y->ch[1]->sum + x->sum;
y->setc(x, 1);
y->push_up();
}
}
void work()
{
int n, m, Q;
int u, v, kk;
scanf("%d%d%d", &n, &m, &Q);
for(int i = 1; i v) swap(u, v);
edge[u].insert(v);
}
int cnt = 0;
for(int i = 1; i v) swap(u, v);
op[cnt++] = ope(kk, u, v);
it = edge[u].find(v);
edge[u].erase(it);
}
}
for(int i = 1; i link(node[u]);
p->link(node[v]);
merge(u, v);
}
}
}
int tcnt = 0;
for(int i = cnt-1; i >= 0; i--) {
int u = op[i].u, v = op[i].v;
if(op[i].kk == 1) {
if(find(u) == find(v)) {
update(node[u], node[v]);
}
else {
Node *p = newnode(1);
p->link(node[u]);
p->link(node[v]);
merge(u, v);
}
}
else {
if(find(u) != find(v)) {
ans[tcnt++] = 0;
}
else {
ans[tcnt++] = ask(node[u], node[v]);
}
}
}
for(int i = tcnt-1; i >= 0; i--) printf("%dn", ans[i]);
}
int main()
{
int _;
scanf("%d", &_);
for(int i = 1; i
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net
1.Insert // 插入一条新的数据,必须全插入 insert into 表名 values (值) // 选择列名插入数据,必须一一对应 insert into 表名 (字段…) values (值…) 2.Update // 可以更条件 upd…