Network
题目大意
给你一个无向连通图，再给出一些添边操作，询问每次添边操作之后图中还剩下多少桥。
Solution
其实很水，缩个点，然后此时图是一棵树，其中每条边都是割边，然后每次加边就把左右端点路径上的所有边都变成非割边即可
树剖维护一下。放这个题的原因就是码量大了一点。
upd：有一个码量很小的生成树的做法。。。我哭了
code:
#include<bits/stdc++.h>
using namespace std;
struct qwq{
int v;
int nxt;
}edge[400010];
int cnt=-1;
int head[200010];
void add(int u,int v){
edge[++cnt].nxt=head[u];
edge[cnt].v=v;
head[u]=cnt;
}
struct tarj{
int ind;
int dfn[200010];
int low[200010];
int col[200010];
bool vis[200010];
int stk[200010];
int top;
int tot;
int x[200010],y[200010];
void init(){
ind=0;
tot=0;
top=0;
memset(low,0,sizeof(low));
memset(dfn,0,sizeof(dfn));
memset(col,0,sizeof(col));
memset(vis,0,sizeof(vis));
}
void tarjan(int u,int fa){
dfn[u]=low[u]=++ind;
stk[++top]=u;
vis[u]=true;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].v;
if(v==fa)continue;
if(vis[v]){
low[u]=min(low[u],dfn[v]);
}
else if(!dfn[v]){
tarjan(v,u);
low[u]=min(low[u],low[v]);
}
}
if(dfn[u]==low[u]){
tot++;
int v;
do{
v=stk[top];
top--;
col[v]=tot;
}while(u!=v);
}
}
}a;
int siz[200010];
int top[200010];
int son[200010];
int fa[200010];
int tid[200010];
int dep[200010];
void dfs1(int u,int fath,int depth){
fa[u]=fath;
dep[u]=depth;
siz[u]=1;
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].v;
if(v==fath)continue;
dfs1(v,u,depth+1);
siz[u]+=siz[v];
if(!son[u]||siz[v]>siz[son[u]])son[u]=v;
}
}
int tim;
void dfs2(int u,int topf){
top[u]=topf;
tid[u]=++tim;
if(son[u])dfs2(son[u],topf);
for(int i=head[u];~i;i=edge[i].nxt){
int v=edge[i].v;
if(v==fa[u]||v==son[u])continue;
dfs2(v,v);
}
}
int sum[400010];
int tag[400010];
void build(int o,int l,int r){
tag[o]=0;
if(l==r){
sum[o]=1;
return;
}
int mid=(l+r)/2;
build(o*2,l,mid);
build(o*2+1,mid+1,r);
sum[o]=sum[o*2]+sum[o*2+1];
}
void pushdown(int o){
if(tag[o]){
sum[o*2]=sum[o*2+1]=0;
tag[o*2]=tag[o*2+1]=1;
tag[o]=0;
}
}
void update(int o,int l,int r,int L,int R){
if(L>R)return;
if(L<=l&&r<=R){
tag[o]=1,sum[o]=0;
return;
}
pushdown(o);
int mid=(l+r)/2;
if(L<=mid)update(o*2,l,mid,L,R);
if(mid<R)update(o*2+1,mid+1,r,L,R);
sum[o]=sum[o*2]+sum[o*2+1];
}
int query(int o,int l,int r,int L,int R){
if(L>R)return 0;
if(L<=l&&r<=R){
return sum[o];
}
pushdown(o);
int mid=(l+r)/2;
int ret=0;
if(L<=mid)ret+=query(o*2,l,mid,L,R);
if(mid<R)ret+query(o*2+1,mid+1,r,L,R);
return ret;
}
void updatetree(int x,int y){
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
update(1,1,a.tot,tid[top[x]],tid[x]);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
update(1,1,a.tot,tid[x]+1,tid[y]);
}
int main(){
memset(head,-1,sizeof(head));
int n,m;
int cas=0;
while(scanf("%d%d",&n,&m)&&n&&m){
printf("Case %d:
",++cas);
a.init();
tim=0;
memset(siz,0,sizeof(siz));
memset(top,0,sizeof(top));
memset(son,0,sizeof(son));
memset(fa,0,sizeof(fa));
memset(tid,0,sizeof(tid));
memset(dep,0,sizeof(dep));
memset(head,-1,sizeof(head));
cnt=-1;
for(int i=1;i<=m;++i){
int u,v;
scanf("%d%d",&u,&v);
add(u,v),add(v,u);
a.x[i]=u,a.y[i]=v;
}
for(int i=1;i<=n;++i){
if(!a.vis[i])a.tarjan(i,-1);
}
memset(head,-1,sizeof(head));
cnt=-1;
for(int i=1;i<=m;++i){
if(a.col[a.x[i]]!=a.col[a.y[i]]){
add(a.col[a.x[i]],a.col[a.y[i]]);
add(a.col[a.y[i]],a.col[a.x[i]]);
}
}
dfs1(1,0,1);
dfs2(1,1);
build(1,1,a.tot);
int q;
scanf("%d",&q);
for(int i=1;i<=q;++i){
int u,v;
scanf("%d%d",&u,&v);
updatetree(a.col[u],a.col[v]);
printf("%d
",sum[1]-1);
}
puts("");
}
}