LuoguLOJ分析考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所以可以考虑把...
LuoguLOJ分析可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$，这样子 ...
CodeforcesLuogu分析可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的权值，修...
BZOJLuogu分析先建出圆方树。圆圆边的边权就为树上的边权，方圆边的边权为圆点到方点父节点的最短路。考虑树上最短路是怎么做的。求出 $\mathrm{lca}$ ，然后答案是 $dis[u]+dis[v]-dis[lca]*2$ ，这里的 $dis$ 是到根的距离。那么圆方树上是一样的，只是要分类讨论一下。如果 $\mathrm{lca}$ 是圆点，那么和树上是一样的。如果 $\math...
LuoguBZOJ分析和仙人掌最大独立集类似，不过难一些。设 $f[i]$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。如果当前边是桥，直接转移，同时更新 $ans$ 。否则当前边在环上，先不处理。假设我们现在在 $u$ ， $v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。我们把这个环找出来单独考虑。先考虑怎么用环上的点更新答案。要求的实际上是 $\...
BZOJ分析我们在 $\mathrm{tarjan}$ 的同时跑 $\mathrm{dp}$ 。设 $f[i][0/1]$ 表示 $i$ 子树中， $i$ 选/不选的最大独立集大小。如果一条边是桥，那么和树上独立集一样的转移。否则，这条边在环上，那么暂时先不转移。假设我们现在正在 $u$ 点，$v$ 点已经访问过了，那么 $v$ 是这个环的顶端， $u$ 是这个环的底端。这时我们可以通过跳父...