点双边双强连通拓展以及一些小技巧

小技巧：

1.关于割点：

点双常常存在割点情况，很难搞，每次dfs都很头疼（不知道割点在哪几个连通块中）
这时候直接每次dfs前手动把bcc内的点都染一个颜色，然后dfs时候看看now和to是不是一个颜色，就可以在一个块中dp了。
这样也可以很快找出块中的边有多少条了！
关键是复杂度还是O(n)，非常棒！

2.关于点双和边双的判断技巧：

利用两种图试试你的思路是不是对的，一种是”沙漏五点“型，另一种是”两点一边“型

3.关于自己制造样例的技巧：

第一种：
和2差不多，创建这种图来验证，不多说
第二种：
单点情况、一条链情况、（点双）考虑全是割点的图（中间三角并且各自向外延伸）。

例题：

1.Tourist Reform
https://www.luogu.com.cn/problem/CF732F
https://www.luogu.com.cn/record/118184808

2.poj2942 Knights of the Round Table
关键在于分析：

原题是憎恨图
这里给的是不憎恨图
（我看着咱们亲爱的ljh把原题原来做的copy过样例过了半天错的摸不着头脑哈哈哈哈哈）

很明显的是，一个点双内的点是可以坐在同一桌上的（因为两边都要连人，所以边双不行）
然后为什么是“存在奇环”整个就行呢？
最基本的点双肯定是一个环。然后可以不断拓展“环”达到大的点双
如果一开始的基本环是偶环，后面拓展的也都是偶环
那么很容易发现，能组出的一桌肯定是偶数的人数
那如果一堆里面有奇环，就肯定可以做到奇数个人组成环，然后每个人都至少包含在一个环中

老师说细节多，我觉得主要是割点有点头疼，但有了技巧1就好做多了！
http://222.180.160.110:1024/contest/4027/problem/7

拓展知识

1.广义圆方树：

知识点：

定义：其实就是将一个点双连通分量拆成一棵树
圆方树中的圆代表着原来的所有的点
圆方树中的方则是新加入的节点，对于任意一个点双会有一个“方”链接所有这个点双里的“圆”
注：原来“圆”之间的边在新的圆方树中不用连起来
这么做了以后，可以得到一棵树，满足以下性质：
1.这棵树任意一个边都是圆和方交替连接的
2.圆方树上任意两个“圆”之间的路径，所经过的所有“圆”表明这两个点在原图中想要到达另外一个点需要经过的必经点
3.圆方树上任意两个“圆”之间的路径，所经过的所有“方”，这个“方”所连接的“圆”，表明这两个点在原图中想要到达另外一个点可以选择经过的点

例题：bzoj3331

其实就是利用了上面的性质2。lca，树上差分,点双完全都是板子,very EZ。
代码：

#include<bits/stdc++.h>
using namespace std;
vector<int>bcc[100005];
vector<int>mp[100005];
int dfn[100005],s[100005],low[100005];
bool cut[100005];
int tt,top,cnt;
int ffpos;//方的编号
vector<int>yfs[200005];
void tarjan(int x,int fa){
	tt++;
	low[x]=dfn[x]=tt;
	s[++top]=x;
	int son=0;
	for(int i=0;i<mp[x].size();i++){
		int to=mp[x][i];
		if(to==fa){
			continue;
		}
		if(!dfn[to]){
			son++;
			tarjan(to,x);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){
				cut[x]=1;
				cnt++;
				ffpos++;
				while(s[top+1]!=to){
					bcc[cnt].push_back(s[top]);
					
					yfs[ffpos].push_back(s[top]);
					yfs[s[top]].push_back(ffpos);
					top--;
				}

				bcc[cnt].push_back(x);
				yfs[ffpos].push_back(x);
				yfs[x].push_back(ffpos);
			}
		}
		low[x]=min(dfn[to],low[x]);
	}
	if(son==0&&x==fa){
		cnt++;
		ffpos++;
		yfs[ffpos].push_back(x);
		yfs[x].push_back(ffpos);//至此建立完成圆方树

		bcc[cnt].push_back(x);
	}
	else if(x==fa&&son<=1){
		cut[x]=0;
	}
}
int dep[200005];
int fa[270005][21];//注：2e18=262,144
int treecf[200005];//用于树上差分
void dfs(int x,int faa){//对圆方树进行dfs求出lca进行树上差分
	dep[x]=dep[faa]+1;
	fa[x][0]=faa;
	for(int i=1;i<=18;i++){
		fa[x][i]=fa[fa[x][i-1]][i-1];//复习过的倍增算法
	}
	for(int i=0;i<yfs[x].size();i++){
		int to=yfs[x][i];
		if(to==faa){
			continue;
		}
		dfs(to,x);
	}
}
int getlca(int x,int y){
	if(dep[x]>dep[y]){
		swap(x,y);//注意不要swap dep数组了 ,x换到深的那里 
	}//让x在上方 
	for(int i=18;i>=0;i--){//还是一定要记住log2向下取整，所以不一定一次就可以跳到，这时候应该跳离depx最近的，所以从大到小美剧，而且每一次跳的比
	//上一次肯定少，所以一遍i即可 
	//另：从小到大枚举不就相当于一次走一位吗 
		if((dep[y]-(1<<i))>=dep[x]){
			y=fa[y][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=18;i>=0;i--){
        if(fa[x][i]==fa[y][i])//因为可能都跳过了 
            continue;
        else{
        	x=fa[x][i];
			y=fa[y][i];
		}
            
    }
    return fa[x][0];
	
}

int ans[200005];
int dfsans(int x,int faa){//差分完后的统计
	int ret=treecf[x];
	for(int i=0;i<yfs[x].size();i++){
		int to=yfs[x][i];
		if(to==faa){
			continue;
		}
		ret+=dfsans(to,x);
	}
	ans[x]=ret;
	return ret;
}
int main(){
	ios::sync_with_stdio(false);
	int n,m,q;
	cin >> n >> m >> q;
	ffpos=n;
	for(int i=1;i<=m;i++){
		int u,v;
		cin >> u >> v;
		mp[u].push_back(v);
		mp[v].push_back(u);
	} 
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			top=0;
			tt=0;
			tarjan(i,i);
		}
	}
	dfs(1,0);//假设1点的fa是0，这样才能做树上差分(不然的话差分fa1=1，导致这里会-2，最后答案为0)
	
	while(q--){
		int u,v;
		cin >> u >> v;
		int lca=getlca(u,v);
		treecf[u]++;
		treecf[v]++;
		treecf[lca]--;
		treecf[fa[lca][0]]--;
		//树上差分
	}
	int k=0;
	k=dfsans(1,0);
	for(int i=1;i<=n;i++){
		cout<< ans[i]<<endl;
	}
	

}