7.11 图联通

传送门

P3436 [POI2006] PRO-Professor Szu

题意描述不太清楚，就算到达 \(n\) 可绕一圈再回来，且数据里图不连通。考虑先求出强连通分量，缩完点后建反图在 \(\text{DAG}\) 上跑 \(\text{dp}\) 计数，注意只记那些从 \(n\) 点开始可达的，如果路径上有一个强连通分量里有边，意味着可以在这个强连通分量里反复走环，它及它的后继都是 \(\text{inf}\)。（输出方案时的点是原图中的，而非缩完点后的）

[ARC092F] Two Faced Edges

求强连通分量，缩点。考虑缩点后 \(\text{DAG}\) 上一条边 \(v \to u\)，翻转后强连通分量个数只能减少，且当且仅当 \(v\) 到 \(u\) 还有一条不经过这个边的路径，以每一个点为起点做一遍拓扑 \(O(n \times (n + m))\) 求出。而对于一个强连通分量里的边 \(v \to u\)，翻转后改变数量当且仅当 \(v \to u\) 是 \(v\) 到 \(u\) 的必经边。考虑怎么求，以每个点为起点顺序枚举它的出边（编号为 \(1\) 到 \(k\)），\(\text{dfs}\) 到每个点记录第一次到该点时来源的起点出边编号，再倒序枚举一次起点出边做一遍 \(\text{dfs}\)，若两次起点 \(v\) 到 \(u\) 的出边编号相同，则该边为必经边，复杂度同样为\(O(n \times (n + m))\)。

P3469 [POI2008] BLO-Blockade

自然可以建圆方树做，但没必要。如果删的不是割点，答案一定是 \((n-1) \times 2\)，如果是割点，设分割出的子树集合是 \(S\)，那么答案是 \(S\) 中的子树大小两两相乘再加 \((n-1) \times 2\)，化简以后是 \(n^2-1- \sum_{i \in S} size_i^2\)。考虑 \(\text{tarjan}\) 走的是一颗搜索树，可以在 \(\text{tarjan}\) 过程中顺便求。

P2860 [USACO06JAN] Redundant Paths G

对于割边两端的点势必只有一条路径。先求边双，缩点后变为一棵树。结论是树上度数为 \(1\) 的点的个数除以 \(2\) 向上取整。

证明：设度数为 \(1\) 的点的集合为 \(S\), 若 \(|S|\) 为偶数，最后连的边数为 \(\frac{|S|}{2}\)，即两个一组对应连边，每次连完边后重新缩点度数为 \(1\) 的点减少 \(2\)，如果一次连边后度数只减少 \(1\)，对应的情况只能是一个度数为 \(3\) 的点下连 \(2\) 条链和一棵子树，连了 \(2\) 条链的端点，这时只要任选一条链的端点与那棵子树中的一个度数为 \(1\) 的点连就可避免这种情况。若 \(|S|\) 为奇数，任选一个度数为 \(1\) 的点连边转化为 \(|S|\) 为偶数的情况。

CF51F Caterpillar

shaber 翻译

一开始看翻译数据范围 \(n \le 20000\)，很奇怪，但自信 \(O(n)\)，快写完时wy提醒我是 \(n \le 2000\)，瞬间破防。但自信写完交，发现直接找直径会漏掉有很多条直径的情况，瞬间破防。

发现答案分为 \(3\) 部分，把所有连通块连在一起，把边双缩成一个点，把挂在直径上的树缩到直径上。但 \(O(n^2)\) 我不会啊，充分利用人类智慧，随机几条直径跑，事实证明正确率非常高。

后来发现确实可以 \(O(n)\)，子树缩到直径上的代价是 \(siz_i-cnt_i\)，其中 \(siz_i\) 为子树大小，\(cnt_i\) 为子树中叶子节点个数。发现这个东西整体考虑非常好求，只跟直径长短和叶子个数有关。

P4606 [SDOI2018] 战略游戏

摧毁的点一定得是割点，否则图还联通。并且摧毁这个点后标记点应在不同的连通块里。这个问题在原图上不好做，求完点双缩点后每次要找标记点在哪个点双里，也比较复杂，于是考虑建圆方树。答案便是圆方树上标记点组成的连通块中圆点个数减去标记点个数。这时候可以一棵虚树直接拍上去，但码量太大了，想一想有没有智慧一点的方法。发现把标记点（假设有 \(k\) 个）按 \(\text{dfs}\) 序排序，每次在相邻两点间（包括第 \(1\) 个点和第 \(k\) 个点）的路径边上加 \(1\)，最后可以发现每条边恰经过两次，由于要求圆点个数，可以把圆方树上圆点到父亲的边边权赋为 \(1\)，方点到父亲的边边权赋为 \(0\)，根是圆点要特判加上 \(2\)。

CF487E Tourists

建圆方树，每个方点上开一个 \(\text{multiset}\)，由于圆方树是一棵非常好的树，每个 \(\text{multiset}\) 里存方点的儿子们的值，每次查两点间路径就能覆盖到所有经过的圆点，除了当 \(\text{lca}\) 为方点时，要加上方点的父亲（没记录进去的的圆点）。在圆方树上树剖实现修改、查询。