圆方树 useful things

圆方树，是解决仙人掌问题的实用方法，假设最初图都是圆点，对于每个环新建一个方点并连接这个环上所有圆点，能很好规避同一个点可能属于很多个环的情况，并且发现build完之后是一棵树

广义圆方树，能够不局限于去解决仙人掌问题，能上升到无向图层面，很好解决图上路径类，等等问题

那么如何建立圆方树？有点类似 \(v-dcc\) ，建立方点，连接当前点双联通分量的所有点，实现通过tarjan算法

但注意 \(v-dcc\) 把整个点双联通分量都缩成一个点了，圆方树还保持着圆点，也就是说圆方树点数是 \(n+k\) ，其中 \(k\) 标号是点双个数

具体实现不详讲，但存在值得注意的细节：

令 \(now\) 为当前 \(dfs\) 到的节点， \(y\) 为其搜索树上的一个儿子。注意， \(now\) 与 \(y\) 在栈中不一定相邻。也就是说，下面两种写法：

1. 弹出栈顶直到弹出 \(now\) 为止；最后再压入 \(now\)
2. 弹出栈顶直到弹出 \(y\) 为止，最后再将虚点向 \(now\) 连边
   前者错误，后者正确。

代码：
圆方树，是解决仙人掌问题的实用方法，假设最初图都是圆点，对于每个环新建一个方点并连接这个环上所有圆点，能很好规避同一个点可能属于很多个环的情况，并且发现build完之后是一棵树

广义圆方树，能够不局限于去解决仙人掌问题，能上升到无向图层面，很好解决图上路径类，等等问题

那么如何建立圆方树？有点类似 \(v-dcc\) ，建立方点，连接当前点双联通分量的所有点，实现通过tarjan算法

但注意 \(v-dcc\) 把整个点双联通分量都缩成一个点了，圆方树还保持着圆点，也就是说圆方树点数是 \(n+k\) ，其中 \(k\) 标号是点双个数

具体实现不详讲，但存在值得注意的细节：

令 \(now\) 为当前 \(dfs\) 到的节点， \(y\) 为其搜索树上的一个儿子。注意， \(now\) 与 \(y\) 在栈中不一定相邻。也就是说，下面两种写法：

1. 弹出栈顶直到弹出 \(now\) 为止；最后再压入 \(now\)
2. 弹出栈顶直到弹出 \(y\) 为止，最后再将虚点向 \(now\) 连边
   前者错误，后者正确。

\(v-dcc\) 和圆方树运用区别何在？后者对于点双内部的处理能够非常方便，而前者似乎处理整个点双对答案的贡献（不考虑单点）会十分好

圆方树的性质：

1. 是树

2. 每条边都是方点和圆点连接边

3. 每个方点对应一个点双联通分量

4. 方点的度数是点双联通分量的大小

5. 圆点是割点才有超过1个儿子，否则只连接一个方点

6. 圆方树上两个点的路径经过的圆点是图上两点之间的必经点

还有一些点双的小性质：对于一个点双的两点，它们之间简单路径的并集等于这个点双集合

圆方树能够很好地将无向图上问题转化为树上问题，进行统计类的时候可能割点会被统计多次，所有一般把方点赋为-1，然后就很好做了

void tarjan(int x){
	++nown;
	dfn[x]=low[x]=++num;
	st.push(x),w[x]=-1; 
	for(int i=head[x];i;i=edge[i].Next){
		int to=edge[i].to;
		if(!dfn[to]){
			tarjan(to);
			low[x]=min(low[x],low[to]);
			if(low[to]>=dfn[x]){
			    addedge2(++diannum,x),addedge2(x,diannum);
				++w[diannum];
				while(1){
					addedge2(diannum,st.top()),addedge2(st.top(),diannum);
					++w[diannum];
					if(st.top()==to){
						st.pop();
						break;
					}
					st.pop();
				}
			}
		}
		else low[x]=min(low[x],dfn[to]);				
	}
}

\(v-dcc\) 和圆方树运用区别何在？后者对于点双内部的处理能够非常方便，而前者似乎处理整个点双对答案的贡献（不考虑单点）会十分好搞

圆方树的性质：

1. 是树

2. 每条边都是方点和圆点连接边

3. 每个方点对应一个点双联通分量

4. 方点的度数是点双联通分量的大小

5. 圆点是割点才有超过1个儿子，否则只连接一个方点儿子

6. 圆方树上两个点的路径经过的圆点是图上两点之间的必经点

还有一些点双的小性质：对于一个点双的两点，它们之间简单路径的并集等于这个点双集合

圆方树能够很好地将无向图上问题转化为树上问题，进行统计类的时候可能割点会被统计多次，所有一般把方点赋为-1，然后就很好做了，等等就不细说了