记录编号	89417	评测结果	AAAAAAAAAA
题目名称	[AHOI 2005] LANE 航线规划	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.555 s
提交时间	2014-03-02 16:00:00	内存使用	9.59 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<map>
#include<set>
#include<cmath>
#include<deque>
using namespace std;
const int SIZEN=30020,SIZEM=100100;
class TARRAY{//改段求点的树状数组
public:
	int n;
	int s[SIZEN];
	void clear(int x){n=x;memset(s,0,sizeof(s));}
	int lowbit(int x){return x&(-x);}
	void prefchange(int x,int t){
		for(int i=x;i>0;i-=lowbit(i)) s[i]+=t;
	}
	void change(int l,int r,int t){
		prefchange(r,t);
		prefchange(l-1,-t);
	}
	int nodeval(int x){
		int ans=0;
		for(int i=x;i<=n;i+=lowbit(i)) ans+=s[i];
		return ans;
	}
};
class REQUEST{
public:
	int cmd;
	int a,b;
};
vector<REQUEST> req;//请求
deque<int> ans;//答案
vector<pair<int,int> > c[SIZEN];//邻接表,first是点,second是是否为桥(桥1否则0)
int N,M;//N个点M条边
int father[SIZEN]={0};
TARRAY condep;
int dfn[SIZEN]={0},low[SIZEN]={0};
int numpst[SIZEN]={0};
int color[SIZEN]={0};
int ufs[SIZEN]={0};//并查集,维护该点所在的边双中最浅的点
int dfslis[SIZEN*10]={0},dfslen=0;
int first[SIZEN]={0};//在序列中首次出现的位置
int ST[SIZEN*2][30]={0};//这个数组一定要是SIZEN*2......因为是DFS序列的长度
int getdeep(int x){//x的深度
	return condep.nodeval(dfn[x]);
}
void STLCA_prepare(void){
	int m=floor(log(dfslen+0.0)/log(2.0));
	for(int i=1;i<=dfslen;i++) ST[i][0]=dfslis[i];
	for(int j=1;j<=m;j++){
		for(int i=1;i<=dfslen;i++){
			if(i+(1<<j)-1>dfslen) continue;
			int x=ST[i][j-1],y=ST[i+(1<<(j-1))][j-1];
			if(getdeep(x)<getdeep(y)) ST[i][j]=x;
			else ST[i][j]=y;
		}
	}
}
int STLCA(int a,int b){
	int l=first[a],r=first[b];
	if(l>r) swap(l,r);
	int m=floor(log(r-l+1.0)/log(2.0));
	int x=ST[l][m],y=ST[r-(1<<m)+1][m];
	return getdeep(x)<getdeep(y)?x:y;
}
int grand(int x){
	return ufs[x]==x?x:ufs[x]=grand(ufs[x]);
}
int bridgenum(int x,int y){//桥数等于缩点后树上的路径长
	int gx=grand(x),gy=grand(y);
	if(gx==gy) return 0;
	return getdeep(gx)+getdeep(gy)-2*getdeep(grand(STLCA(gx,gy)));
}
void addedge(int x,int y){//加边
	int gx=grand(x),gy=grand(y);
	if(gx==gy) return;
	int anc=grand(STLCA(gx,gy)),ad;//公共祖先
	ad=getdeep(anc);
	vector<int> st;
	for(int now=gx;now!=anc;now=grand(father[now])) st.push_back(now);
	for(int i=st.size()-1;i>=0;i--) condep.change(dfn[st[i]],dfn[st[i]]+numpst[st[i]]-1,ad-getdeep(st[i])),ufs[st[i]]=anc;
	st.clear();
	for(int now=gy;now!=anc;now=grand(father[now])) st.push_back(now);
	for(int i=st.size()-1;i>=0;i--) condep.change(dfn[st[i]],dfn[st[i]]+numpst[st[i]]-1,ad-getdeep(st[i])),ufs[st[i]]=anc;
	//分别把两条链上的点都提上去,因为此前已经将每个边双点的深度置为一样,因此它能正确地修改子树的深度
}
void offlinework(void){//离线处理
	for(int i=req.size()-1;i>=0;i--){
		if(req[i].cmd==1) ans.push_front(bridgenum(req[i].a,req[i].b));
		else if(req[i].cmd==0) addedge(req[i].a,req[i].b);
	}
}
void markDCC(int x,int sst,int dep){//对双连通分量进行标号,当前DCC中最浅的点是sst
	if(color[x]) return;
	color[x]=1;
	ufs[x]=sst;
	condep.change(dfn[x],dfn[x],dep);
	dfslis[++dfslen]=x;first[x]=dfslen;
	for(int i=0;i<c[x].size();i++){
		if(color[c[x][i].first]) continue;
		if(c[x][i].second) markDCC(c[x][i].first,c[x][i].first,dep+1);
		else markDCC(c[x][i].first,sst,dep);
		dfslis[++dfslen]=x;
	}
}
int timer=0;
void Tarjan(int x){
	color[x]=-1;
	dfn[x]=low[x]=++timer;
	numpst[x]=1;
	for(int i=0;i<c[x].size();i++){
		int v=c[x][i].first;
		if(color[v]==0){
			father[v]=x;
			Tarjan(v);
			numpst[x]+=numpst[v];
			low[x]=min(low[v],low[x]);
		}
		else if(color[v]==-1&&v!=father[x]) low[x]=min(low[x],dfn[v]);
		if(dfn[x]<low[v]) c[x][i].second=1;//标记为桥
	}
}
set<pair<int,int> > edges;
void init(void){
	scanf("%d%d",&N,&M);
	condep.clear(N);
	int u,v;
	pair<int,int> pr;
	for(int i=1;i<=M;i++){
		scanf("%d%d",&u,&v);
		if(u>v) swap(u,v);
		pr=make_pair(u,v);
		edges.insert(pr);
	}
	REQUEST nc;
	while(true){
		scanf("%d",&nc.cmd);
		if(nc.cmd==-1) break;
		scanf("%d%d",&nc.a,&nc.b);
		if(nc.a>nc.b) swap(nc.a,nc.b);
		req.push_back(nc);
		if(nc.cmd==0){//破坏一条边
			pr=make_pair(nc.a,nc.b);
			edges.erase(edges.find(pr));
		}
	}
	set<pair<int,int> >::iterator key;
	for(key=edges.begin();key!=edges.end();key++){
		u=key->first,v=key->second;
		c[u].push_back(make_pair(v,0));
		c[v].push_back(make_pair(u,0));
	}
}
int main(){
	freopen("lane.in","r",stdin);
	freopen("lane.out","w",stdout);
	init();//此时,c中存的就是所有询问之后的边信息
	Tarjan(1);
	memset(color,0,sizeof(color));
	markDCC(1,1,0);
	STLCA_prepare();
	offlinework();
	for(int i=0;i<ans.size();i++) printf("%d\n",ans[i]);
	return 0;
}