圆方树

分为圆方树和广义圆方树。前者处理仙人掌，后者处理一般无向图。

只学了后一个。

广义圆方树

在无向图中进行(mathrm{Tarjan})，对于每个点双构建一个方点，方点向点双中的所有点连边。

这就建好了一张新图。

对于一般的题，可以在圆点上维护这个点的信息，方点上维护这个点双的信息。这样就可以支持一些对无向图路径的操作了。

贴一张网上找来的图

观察一些性质：

给定一张 (n) 个点 (m) 条边的无向图，请求出三元组 ((s,c,f)) 的个数，使得存在一条从 (s) 到 (f) 经过点 (c) 的简单路径。(n,mleq 2cdot 10^5)。

先求出圆方树。

考虑枚举 (s,f)，那么合法的 (c) 个数就是 (s) 到 (f) 间的点双的点数和减去 (s,f) 这两个点。

设方点权值为点双的点数，圆点的权值为 (-1)。

那 (c) 的数量就是 (s,f) 两点之间的点权和。

考虑枚举中点 (c)，那点 (c) 的贡献就是经过 (c) 的路径数目*它的权值。

树形(mathrm{DP})即可

给定一张 (n) 个点 (m) 条边的无向联通图，每个点有权值 (w_i)。要求支持：带修改，求两点之间所有路径上的最小权值。

如果不带修改怎么办？

还是求出圆方树。

把方点的点权设为点双中的最小权值，圆点权值即为本身的权值。

问题就变成了询问链上最小值。树剖即可。

加上修改呢？

如果还按照刚才的方法维护，假设一个点是割点，同时属于很多点双，那么在修改这个点的权值时，会顺便修改与它相连的所有方点的权值。如果这是个菊花图就卡掉了。

考虑一种套路，就是让每个点维护的信息少一点点，然后修改的复杂度就不那么大了，例子就是用(mathrm{lct})做(mathrm{Qtree6})。

这里也可以这样做，具体是让每个方点的权值不包含它的父亲（它的父亲肯定是圆点以及肯定在这个点双中），也就是说每个圆点的值只对圆方树上它的父亲有贡献。这样如果修改一个点的复杂度就降下来了。

那再回来考虑询问因为少维护了一些信息会出什么(mathrm{bug})，发现就是当(mathrm{lca})为方点时，会少算这个方点的父亲的点权，特判一下就好了。

所以拿圆方树+树剖+(mathrm{mutiset})就可以解决本题了。