题目描述
小强要在个孤立的星球上建立起一套通信系统。这套通信系统就是连接个点的一个树。 这个树的边是一条一条添加上去的。在某个时刻，一条边的负载就是它所在的当前能够 联通的树上路过它的简单路径的数量。
现在，你的任务就是随着边的添加，动态的回答小强对于某些边的负载的询问。

离线
在查询的时候，如果我们把这条边删掉，那么答案就很好求
观察到有删、加边，用线段树分治即可
具体而言，对于每一个查询，时间为，和上一次查询（若没有则是添加它的时间），在加入这条边
最后一次查询加入到
可撤销并查集即可

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int Maxn=1e5;
struct Query {
    int x,y,id;
};
vector<int>r[Maxn+5];
map<pii,int>id;
pii e[Maxn+5];
int l[Maxn+5],n,q;
struct UnionSet {
    int s[Maxn+5],top;
    int father[Maxn+5],size[Maxn+5];
    void init() {
        for(ri i=1;i<=n;i++)father[i]=i,size[i]=1;
    }
    int getfather(int v) {
        return father[v]==v?v:getfather(father[v]);
    }
    void merge(int x,int y) {
        int fx=getfather(x),fy=getfather(y);
        if(size[fx]<size[fy])swap(fx,fy);
        s[++top]=fy;
        father[fy]=fx,size[fx]+=size[fy];
    }
    void del(int k) {
        while(top>k) {
            int t=s[top--];
            size[father[t]]-=size[t];
            father[t]=t;
        }
    }
}us;
struct SegTree {
    #define ls(p) (p<<1)
    #define rs(p) (p<<1|1)
    #define mid (((l)+(r))>>1)
    vector<pii>v[Maxn<<2];
    Query q[Maxn+5];
    void change(int p,int l,int r,int L,int R,pii d) {
        if(L>R)return ;
        if(L<=l&&r<=R) {
            v[p].push_back(d);return ;
        }
        if(L<=mid)change(ls(p),l,mid,L,R,d);
        if(R>mid)change(rs(p),mid+1,r,L,R,d);
    }
    void solve(int p,int l,int r) {
        int size=(int)v[p].size(),u=us.top;
        for(ri i=0;i<size;i++)us.merge(v[p][i].x,v[p][i].y);
        if(l==r) {
            if(q[l].id) {
                ll ans=1ll*us.size[us.getfather(q[l].x)]*us.size[us.getfather(q[l].y)];
                printf("%lld\n",ans);    
            }
        }
        else {
            solve(ls(p),l,mid);
            solve(rs(p),mid+1,r);
        }
        us.del(u);
    }
}t;
int main() {
    scanf("%d%d",&n,&q);
    int cnt=0,tot=0;
    for(ri i=1;i<=q;i++) {
        char c=getchar();
        while(c!='A'&&c!='Q')c=getchar();
        pii s;
        scanf("%d%d",&s.x,&s.y);
        if(c=='A') {
            e[++cnt]=s;id[s]=cnt;l[cnt]=i;
        }
        else {
            r[id[s]].push_back(i);t.q[i]=(Query){s.x,s.y,++tot};
        }
    }
    for(ri i=1;i<=cnt;i++) {
        int size=(int)r[i].size(),now=l[i];
        for(ri j=0;j<size;j++) {
            t.change(1,1,q,now,r[i][j]-1,e[i]);
            now=r[i][j]+1;
        }
        t.change(1,1,q,now,q,e[i]);
    }
    us.init();
    t.solve(1,1,q);
    return 0;
}

在线
还是考虑删边
我们有两种思路

处理只不添加第条边的图，每次查询 回退到第条边，再回加
这两种方法复杂度都很高
那结合呢？
分块
每个操作记录在一块内
每个操作建一个新图，表示不加如这条边，而加入其余所有已加边的图
每次查询找到这个操作对应的块
在对应块的图上将除这条边外所有这块内的边加入
这就可以求了
可撤销并查集回退一下
注意每一次加边要将之前所有的块的图加入这条边，新建一个块要将除这块外之前所有的边加入
时间复杂度，空间复杂度

#include <bits/stdc++.h>
#define ri register int
#define ll long long
#define pii pair<int,int>
#define x first
#define y second
using namespace std;
const int Maxn=1e5;
const int Maxm=320;
map<pii,int>id;
vector<pii>v[Maxm+5];
int n,q,T;
int bel[Maxn+5],Block;
static char buf[30000000],*p1=buf,*p2=buf,obuf[30000000],*p3=obuf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define putchar(x) (p3-obuf<1000000)?(*p3++=x):(fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=x)
template<typename item>
inline void read(register item &x) {
    x=0;register char c=getchar();
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
static char cc[7000000];
template<typename item>
inline void print(register item x) {
    ri len=0;
    do {cc[len++]=x%10+'0',x/=10;}while(x);
    while(len--)putchar(cc[len]);
}
struct UnionSet {
    int s[Maxn+5],top;
    int father[Maxn+5],size[Maxn+5];
    inline void init() {
        for(ri i=1;i<=n;i++)father[i]=i,size[i]=1;
    }
    inline int getfather(int v) {
        return father[v]==v?v:getfather(father[v]);
    }
    inline void merge(int x,int y) {
        int fx=getfather(x),fy=getfather(y);
        if(fx!=fy) {
            if(size[fx]<size[fy])swap(fx,fy);
            s[++top]=fy;
            father[fy]=fx,size[fx]+=size[fy];
        }
    }
    inline void del(int k) {
        while(top>k) {
            int t=s[top--];
            size[father[t]]-=size[t];
            father[t]=t;
        }
    }
}us[Maxm+5];
inline ll query(int x,int y) {
    int block=bel[id[make_pair(x,y)]];
    int u=us[block].top;
    for(ri i=0;i<(int)v[block].size();i++) {
        pii t=v[block][i];
        if(t.x!=x||t.y!=y)us[block].merge(t.x,t.y);
    }
    ll ans=us[block].size[us[block].getfather(x)]*us[block].size[us[block].getfather(y)];
    us[block].del(u);
    return ans;
}
inline void build() {
    ++Block;
    us[Block].init();
    for(ri i=1;i<Block;i++) {
        for(ri j=0;j<(int)v[i].size();j++) {
            pii t=v[i][j];
            us[Block].merge(t.x,t.y);
        }
    }
}
int main() {
    read(n),read(q),read(T);
    ll ans=0;
    int cnt=0,Size=320;
    build();
    for(ri i=1;i<=q;i++) {
        char c=getchar();
        while(c!='A'&&c!='Q')c=getchar();
        int x,y;
        read(x),read(y);
        if(T)x^=ans,y^=ans;
        if(c=='A') {
            pii t;t.x=x,t.y=y;
            for(ri j=1;j<Block;j++)us[j].merge(t.x,t.y);
            v[Block].push_back(t);
            id[t]=++cnt;bel[cnt]=(cnt-1)/Size+1;
            if(cnt%Size==0)build();
        }
        else print(ans=query(x,y)),putchar('\n');
    }
    fwrite(obuf,p3-obuf,1,stdout);
    return 0;
}