点双边双强连通拓展以及一些小技巧
目录小技巧：
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;
}
}