题意:给出一张N个点,M条边的无向图,有两个操作:
1.删除(u, v)间的一条边
2.如果删除(u, v)间的一条边可使其不连通,找出这样的边的个数,就是找(u, v)间桥的个数
询问时 ,处理到同一条重链 , 要( l+1, r ),这样就是边权
思路:首先离线这些操作,时光倒流从最终状态逆着加边加回原图,可以考虑用并查集建树,然后以树作为最终状态,再树链剖分预处理下,建一颗线段树维护区间和(叶子值为1代表当前边为桥),如果有边(u, v)要加入,那就将(u, v)这段区间的所对应的线段树叶子值全清零,并设置标记数组,因为已更新过的点不用再访问
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int mxn=100010;
struct edge {
int v,nxt;
} e[mxn<<1];
struct No{
int from,to;
bool operator < (const No &c)const {
return from == c.from ? to < c.to : from < c.from;
}
};
multiset <No> s;
int hd[mxn],mct=0;
void add_edge(int u,int v) {
e[++mct].v=v;
e[mct].nxt=hd[u];
hd[u]=mct;
}
//邻接表
struct node {
//结点u的 父亲 重儿子
int fa,son;
int size,dep,top;//子树大小 深度 重链顶点
int w,e;//编号 对应线段树的结尾
} tr[mxn];
//树剖结点
struct segtree {
LL smm,mk;
} st[mxn<<2];
int sz=0;
//线段树
int n,M,rt;
int w[mxn];//初始值
//
void DFS1(int u) {
tr[u].size=1;
tr[u].son=0;
for(int i=hd[u]; i; i=e[i].nxt) {
int v=e[i].v;
if(v==tr[u].fa)continue;
tr[v].fa=u;
tr[v].dep=tr[u].dep+1;
DFS1(v);
tr[u].size+=tr[v].size;
if(tr[v].size>tr[tr[u].son].size)
tr[u].son=v;
}
return;
}
void DFS2(int u,int top) { //当前点,当前链的顶点
tr[u].top=top;
tr[u].w=++sz;//把树边挂上线段树
if(tr[u].son) {
DFS2(tr[u].son,top);//扩展搭建重链
for(int i=hd[u]; i; i=e[i].nxt) {
int v=e[i].v;
if(v!=tr[u].fa && v!=tr[u].son)
DFS2(v,v);//搭建轻链
}
}
tr[u].e=sz;//当前点对应的线段树结尾
return;
}
void build(int l,int r,int k){
st[k].mk = 0;
if(l==r){
st[k].smm = 1;
return ;
}
int mid = (l+r)>>1;
build(l,mid,k<<1);
build(mid+1,r,k<<1|1);
st[k].smm = st[k<<1].smm + st[k<<1|1].smm;
}
void update(int L,int R,int l,int r,int k) { //区间变为0
if(L<=l && r<=R) {
st[k].mk=1;
st[k].smm = 0;
return;
}
int mid=(l+r)>>1;
if(st[k].mk) {
st[k<<1].mk = 1;
st[k<<1].smm=0;
st[k<<1|1].mk=1;
st[k<<1|1].smm=0;
st[k].mk=0;
}
if(L<=mid)update(L,R,l,mid,k<<1);
if(R>mid)update(L,R,mid+1,r,k<<1|1);
st[k].smm=(st[k<<1].smm+st[k<<1|1].smm);
return;
}
int query(int L,int R,int l,int r,int k) {
if(L<=l && r<=R)return st[k].smm;
int mid=(l+r)>>1;
if(st[k].mk) {
st[k<<1].mk = 1;
st[k<<1].smm=0;
st[k<<1|1].mk=1;
st[k<<1|1].smm=0;
st[k].mk=0;
}
LL res=0;
if(L<=mid)res=(res+query(L,R,l,mid,k<<1));
if(R>mid)res=(res+query(L,R,mid+1,r,k<<1|1));
return res;
}
// 表示求树从x到y结点最短路径上所有节点权值变为0
void find(int x,int y) {
int f1=tr[x].top,f2=tr[y].top;
while(f1!=f2) {
if(tr[f1].dep<tr[f2].dep) {
update(tr[f2].w,tr[y].w,1,n,1);
y=tr[f2].fa;
f2=tr[y].top;
} else {
update(tr[f1].w,tr[x].w,1,n,1);
x=tr[f1].fa;
f1=tr[x].top;
}
}
if(x==y)return ;
if(tr[x].dep<tr[y].dep)update(tr[ x ].w+1,tr[y].w,1,n,1);
update(tr[y].w+1,tr[x].w,1,n,1);
}
int query(int x,int y) {
int f1=tr[x].top,f2=tr[y].top;
int ans = 0;
while(f1!=f2) {
if(tr[f1].dep<tr[f2].dep) {
ans+=query(tr[f2].w,tr[y].w,1,n,1);
y=tr[f2].fa;
f2=tr[y].top;
} else {
ans+=query(tr[f1].w,tr[x].w,1,n,1);
x=tr[f1].fa;
f1=tr[x].top;
}
}
if(x==y)return ans;
if(tr[x].dep<tr[y].dep)return (ans+query(tr[x].w + 1,tr[y].w,1,n,1));
return (ans+query(tr[y].w + 1,tr[x].w,1,n,1));
}
int Fa[mxn],Rank[mxn];
int find(int a){
if(Fa[a]!=a)Fa[a] = find(Fa[a]);
return Fa[a];
}
void unio(int a,int b){
int t1 = find(a),t2 = find(b);
if(Rank[t1]>Rank[t2]){
Fa[t2] = t1;
Rank[t1]++;
}else {
Fa[t1] = t2;
Rank[t2]++;
}
}
int vis[mxn];
struct NN{
int op;
int l,r;
}q[mxn];
int ans[mxn];
int main() {
rt = 1;
int Q,t,cnt=1;
scanf("%d",&t);
while(t--) {
scanf("%d %d %d",&n,&M,&Q);
int i,j;
for(i=1; i<=n; i++) {
Fa[i] = i; Rank[i] = 1;
}
s.clear();
int x,y,k;
mct = 0; sz = 0;
memset(hd,0,sizeof(hd));
memset(st,0,sizeof(st));
int id = 0;
for(i=1; i<=M; i++) {
No now;
scanf("%d %d",&now.from,&now.to);
if(now.from>now.to)swap(now.from,now.to);
s.insert(now);
}
for(int i=1;i<=Q;i++){
scanf("%d %d %d",&q[i].op,&q[i].l,&q[i].r);
if(q[i].l>q[i].r)swap(q[i].l,q[i].r);
if(q[i].op==1){
s.erase(s.find(No{q[i].l,q[i].r}));
}
}
memset(vis,0,sizeof(vis));
for(multiset<No>::iterator it = s.begin();it!=s.end();it++){
id++;
No now = (*it);
if(find(now.from)==find(now.to))continue;
add_edge(now.from,now.to);
add_edge(now.to,now.from);
unio(now.from,now.to);
vis[id] = 1;
}
sz=tr[0].size=tr[rt].dep=0;
DFS1(rt);
DFS2(rt,rt);
build(1,sz,1);
id = 0;
for(multiset<No>::iterator it = s.begin();it!=s.end();it++){
id++;
if(vis[id])continue;
No now = (*it);
x = now.from, y = now.to;
find(x,y);
}
for(int i=Q;i>=1;i--){
if(q[i].op==2){
ans[i] = query(q[i].l,q[i].r);
}else {
find(q[i].l,q[i].r);
}
}
printf("Case #%d:\n",cnt++);
for(int i=1;i<=Q;i++){
if(q[i].op==2){
printf("%d\n",ans[i]);
}
}
}
return 0;
}
/*
100
10 12 14
1 2
1 3
2 4
2 5
3 6
4 7
4 8
5 8
6 10
7 9
8 9
8 10
1 10 6
1 5 8
1 7 9
2 4 5
2 7 9
2 4 8
2 2 5
2 1 2
2 3 6
2 10 1
2 10 6
2 3 10
2 5 10
2 7 4
*/