洛谷4606 [SDOI2018]战略游戏
Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所...
Luogu LOJ 分析 考虑哪些点是满足条件的。可以发现任意两个关键点路径上的割点都满足条件。 于是可以考虑广义圆方树，因为两个点路径上的割点即对应在圆方树路径上的圆点。 又因为关键点两两之间路径的并就等于这些关键点的虚树，所以我们把问题转化成了求虚树上圆点个数（等价于求点权和）。 这个并不好做，但是我们知道边权和是很好求的（等于所有点按 DFS 序排序后相邻两个点的距离之和再除以二），所...
Luogu LOJ 分析 可以发现 $s$ 到 $t$ 的所有简单路径的并相当于 $s$ 到 $t$ 经过的所有点双连通分量（这里一条边也算点双）的并。 那么对于一对 $(s,t)$，满足条件的 $c$ 的数量就等于 $s$ 到 $t$ 经过的所有点双的大小之和减 $2$。 考虑怎么快速求两点之间所有点双大小之和。容易想到广义圆方树，可以想到将方点的权值设成点双大小，圆点的权值设成 $-1$...
Codeforces Luogu 分析 可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。 从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的...
Luogu 分析 设 $f_i$ 表示 $i$ 子树中以 $i$ 为端点的最长链的长度。 如果当前边是桥，直接转移，同时更新 $ans$ 。 否则当前边在环上，先不处理。 假设我们现在在 $u$，$v$ 已经被访问过了。那么 $u$ 是这个环的底端， $v$ 是这个环的顶端。 我们把这个环找出来单独考虑。 先考虑怎么用环上的点更新答案。 要求的实际上是 $\max\{f_i+f_j+dis(...