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$ 是这个环的底端。这时我们可以通过跳父...