（广义）圆方树

圆方树用于解决仙人掌（没有一条边在两个环上的无向连通图）上的一些问题，广义圆方树用于解决无向图中的一些问题。（不过目前没怎么做过题，不知道广义不广义有啥区别）

博客

前置技能

tarjan 算法求点双

一定要先学好 tarjan 算法啊！！ 吃够了基础不牢的苦

圆方树的构建

和 tarjan 点双缩点不一样的是，我们并不去“复制”割点，甚至都不用显式地标出割点，我们直接用一个“方点”代表一个DCC，“方点”向DCC上的所有点连边，以保证每个点只出现一次。特别的，当DCC中只有两个点的时候，我们更倾向于不建“方点”，因为这种情况不会出环，只是个没有割点的DCC

至于边权，就可能是具体问题具体分析了。（因为我目前就做对过一道题）。比如P5236 【模板】静态仙人掌
这道例题，求仙人掌上两点最短路，我们的处理方法是：圆圆边（圆点-圆点）边权就是原图边权；圆方边边权是圆点到方点的父亲（即DCC里面靠上的那个割点)在原图中的最短距离。查询的话用树剖lca的方法解决，如果lca是圆点，就照常做；如果是方点，就要把经过那个环的两种路径都考虑一下。

总之，细节很多，需要一些技巧。不过如果不考虑边权的话，圆方树还是比较友好的。

代码：

void tarjan(int cur) {
	dfn[cur] = low[cur] = ++dcnt;
	stk[++stop] = cur;
	for (register int i = head[cur]; i; i = e[i].nxt) {
		int to = e[i].to;
		if (!dfn[to]) {
			pre_val[to] = e[i].val;
			tarjan(to);
			MIN(low[cur], low[to]);
			if (low[to] >= dfn[cur]) {
				if (stk[stop - 1] == cur) {
					--stop;
					Addedge(cur, to, e[i].val);
					Addedge(to, cur, e[i].val);
					continue;
				}
				++dtot;
				int p = stk[stop], S = lval[p];
				for (register int j = stop; stk[j] != cur; --j)
					sum[stk[j]] = S, S += pre_val[stk[j]];
				while (stk[stop] != cur) {
					int tmp = stk[stop--];
					int evl = min(sum[tmp], S - sum[tmp]);
					Addedge(tmp, dtot, evl);
					Addedge(dtot, tmp, evl);
				}
				Addedge(cur, dtot, 0), Addedge(dtot, cur, 0); sum[cur] = 0;
				sum[dtot] = S;
			}
		} else {
			if (dfn[to] < low[cur])	low[cur] = dfn[to], lval[cur] = e[i].val;
		}
	}
}
int Find(int x, int lca) {//找到 x - lca 路径中lca下面的那个点的编号
	int lst = 0;
	while (top[x] != top[lca])	lst = top[x], x = fa[top[x]];
	return x == lca ? lst : son[lca];
}

...

int main() {
      ...      
                int lca = get_lca(u, v);
		if (lca <= n)
			printf("%d
", dis[u] + dis[v] - (dis[lca] << 1));
		else {
			int ans = dis[u] + dis[v];
			u = Find(u, lca), v = Find(v, lca);
			ans = ans - dis[u] - dis[v];
			if (sum[u] < sum[v])	swap(u, v);
			ans += min(sum[u] - sum[v], sum[lca] - (sum[u] - sum[v]));
			printf("%d
", ans);
		}
      ...
}

待续