这边工作日都上不了 \(3\) 月好像死了一样。
tricks
-
强连通分量缩点后必然是 DAG，如果显然是结论题一般讨论 \(indeg/outdeg = 0\) 的点。
-
图上问题如果边双后等价可以转化为树上问题。
-
同理如果点双后等价可以圆方树上做；也可以：点双一般保证子图联通，可以分类讨论割点。
-
圆方树计数时一般会给圆点方点放合适的权值，然后直接计算 \((u ,v)\) 的在圆方树上的简单路径的边权总和。
割边/边双
https://www.luogu.com.cn/problem/CF1000E
边双内的点显然没有必然经过的边，于是建边双树那么就是求树上 \(dis(u ,v)\) 的最大值，直接求直径即可。
代码懒得打。
https://www.luogu.com.cn/problem/P2860
边双，建边双树，显然上限为叶子个数 \(leaf\)，都连根即可，然后考虑连接第 \(i\) 个叶子和第 \(leaf - i + 1\) 个叶子，如果 \(leaf\) 为奇数剩下的连根即可，考虑分是否在根的同一子树下讨论，容易发现取得到，答案为 \(\lceil \frac{leaf}{2}\rceil\)。
https://www.luogu.com.cn/problem/P3469
去掉节点 \(i\) 容易想到割点，然后分类讨论：
-
\(i\) 不是割点，显然只有 \((i ,u) ,(u ,i)\)（\(u \neq i\)）合法，答案为 \(2(n - 1)\)。
-
\(i\) 是割点，假设符合的点对是 \((x ,y)\)：
-
\(x/y\) 在 \(i\) 子树内且不包括 \(i\)，\(y/x\) 子树外且不包括 \(i\)，贡献 \(2(sz_i - 1)(n - sz_i)\)。
-
\(x,y\) 在 \(i\) 子树内且不包括 \(i\)，遍历子树好求。
-
\(x ,y\) 一个是 \(i\)，贡献 \(2(n - 1)\)。
-
没了，树上简单计数。
割点/点双/圆方树
https://www.luogu.com.cn/problem/P3225
坍塌点，点删除，割点。
点双内的点互相到达，然后分类讨论：
-
点双内原图割点数为 \(0\)，只要设 \(2\) 个救援点即可，不是 \(1\) 个是为了防止那个塌了，方案数贡献为 \(\binom{sz}{2}\)。
-
点双内原图割点数为 \(1\)，只要在非割点地方设置 \(1\) 个救援点即可。如果塌了割点和其他点双断了，设置的这个可以救援；如果塌了救援点可以到其他点双分量里。
-
点双内原图割点数为 \(\ge 2\)，不用设置，可以到其他点双。
显然在一个连通子图内，点双相互联通，第一、二类数量至少为 \(1\)，因此存在正确性。
https://www.luogu.com.cn/problem/P4630
确定了 \(s,f\) 后 \(c\) 可能数量即为 \(s,f\) 简单路径的并集去除 \(s,f\) 的大小。
有个结论就是点双后放到圆方树上，\(s,f\) 路径上所有方点相邻的原点就是并集大小。
给方点赋值点双内点数量的权值，圆点赋上 \(-1\)，\(dis(u ,v)\) 即为所求，时间复杂度 \(\mathcal O(n^2 \log n)\) 需要优化。
经典 trick，枚举其中一个点计算贡献，由于点的贡献是独立的，只要计算经过它的边数即可，简单树上计数，类上面的 https://www.luogu.com.cn/problem/P3469。
https://www.luogu.com.cn/problem/CF487E
路径并集的最小值，圆方树，方点点权为点双内点权最小值，树剖 + SGT 即可维护。
修改比较困难，可能需要修改很多个节点，从而 TLE。
由于圆方树是一棵树，我们令方点权值为儿子原点的最小值，然后直接修改即可。维护方点内所有儿子的权值（因为要删除修改前的值）用 multiset 即可。
注意一点点小细节。
https://www.luogu.com.cn/problem/P8456
强连通分量
https://www.luogu.com.cn/problem/P2341
\(u\) 喜欢 \(v\) 连接 $u \to v $ 的有向边，容易想到强连通分量缩点，一个强连通分量的奶牛肯定互相喜欢，答案即为所点后出度为 \(0\) 的包含的奶牛数量。
https://www.luogu.com.cn/problem/P1073
无向边拆成两条有向边，然后一个强连通分量可以一直走，我们可以在前面买入后面卖出，强连通分量缩点后是 DAG，我们枚举第 \(i\) 个强连通分量卖出，直接 DAG 上 DP 出前面的最小值 \(mn\)，\(mx_i - mn\) 即为可能答案，比最大值即可。
https://www.luogu.com.cn/problem/P7251
第一问简单，强连通分量的最大大小即为答案。
第二问考虑缩点成 DAG，讨论入度为 \(0\) 和出度为 \(0\) 的点，只要出度为 \(0\) 的连向没连过的入度为 \(0\) 的点即可，剩下的没连的连起来，不妨设 $indeg = 0 $ 有 \(x\) 个，\(outdeg = 0\) 有 \(y\) 个：
-
\(x > y\)：
-
出度为 \(0\) 连向入度为 \(0\) 的，贪心地肯定连向不同的 DAG 子图。
-
剩下 \(x - y\) 个入读为 \(0\) 的用 \(x - y - 1\) 条边连接，以及 \(1\) 条边连接已强连通分量的。
-
画图不难验证，总数为 \(x\)。
-
-
\(x < y\) 同理为 \(y\)。
因此答案为 \(\max(x ,y)\)。