[AGC059C] Guessing Permutation for as Long as Possible（2-sat）
这个东西十分智障，只需要对于所有 \(a, b, c\)，如果询问顺序是 \((a, b), (b, c), (a, c)\)，那么不能 \(a<b<c\) 或 \(a>b>c\)。其它的情况（一条链）你一看发现肯定需要出现上述情况，那么这就是充要条件。
你一看你直接对所有询问当作 2-sat 的变量去拆点就能连出来一张无向图，既然是无向图那么连 2-sat 都不用，直接是一个并查集题目。最终答案 \(2^{block/2}\) 其中 \(block\) 是连通块数量，连通块一定是对称的。另外根据我们的过程，一定不会有环。
[NOI2017] 游戏
skipped
[CF587D] Duff in Mafia（2-sat）
这一题的限制超强。对于一个点，你最多只能破坏一条与之相连的边，且同一个点上的同色边不能超过两条，如果有两条同色边则它们必须破坏一条。这就太离谱了，读到这里已经可以前后缀优化 2-sat 建图了（可能还要写个二分）。然而因为同一个点上的同色边不能超过两条，所以你还能发现同色中一定是一堆环和链，环比较简单，链有一个链头可能要和其它人分讨，也是 2-sat 解决的。
[CF1137C] Museums Tour（SCC）
分层图，缩点。你发现城市 \(x\) 的周 \(a\) 与城市 \(x\) 的周 \(b\) 这两个状态不可能出现：它们不在同一 SCC，但是前者能走到后者。因为既然已经能走回城市 \(x\) 的周 \(b\) 了，那么你再重复走 \(d-1\) 轮就能回去周 \(a\) 了。于是就变成 DAG 上 DP。
无标题（SCC）
有⼀张 \(n\) 个点的图，初始没有边。
接下来有 \(m\) 条有向边依次加入图中，保证没有自环，且任意 \(i,j\) 间最多有⼀条边。
每次加入之后，查询如果我们在图中添加⼀些边使得图构成竞赛图，其强连通分量个数的最小值。
\(n\leq 2\times 10^5, m\leq 2\times 10^6\)。
定理：补图上的连通块可以定向成为强连通分量，除非其大小为 \(2\)。
证明：考虑随意定向，此时是竞赛图，其缩点后为一条链。考虑最后一个 SCC，因为补图是连通的，所以它肯定有一条边往回连了，可以反向之，然后递归下去，可以证明原结论。
所以可以先算 \(m\) 条边的答案，反复缩点缩成竞赛图（可能有 SCC 的大小为 \(2\) 要记下）。往前处理询问时，相当于补图上加边，那就能把一个区间的 SCC 缩起来了。
（待修订）[IOI2019] 景点划分（dfs 树）
钦定 \(a\leq b\leq c\)。想象一棵树怎么做，我们只需要找出重心，如果它有 \(\geq a\) 的子树就做完了，如果没有（这里要再证一下，结论是无解）
对于一般图，随机求 dfs 树，求出其重心，如果它有 \(\geq a\) 的子树就做完了。如果没有，考虑这么一个东西，因为 dfs 没有横叉边，这个重心的子树只可能往它头上有连边。维护点集 \(S\)，先将重心头上的点加入 \(S\)，再考虑重心的子树，如果有往上跨过重心的返祖边则也加入 \(S\)，直到 \(|S|\geq a\) 时就有解了。我们其实是在合并子树，显见，直到有解的时候，\(|S|<2a\)，推出剩下的点有 \(\geq n-2a\) 个，而
（待修订）[QOJ3301] Economic One-way Roads（耳分解）
（待修订）[QOJ8056] Travel 2（dfs 树）
因为上面这两题赵老师在八中讲了
[UNR #5] 获奖名单
这个东西的核心是将其看作从两端向中间匹配。建出 \(m+1\) 个点，第 \(0\) 个点表示现在左右两端已经匹配，第 \(i\) 个点表示有一端多了一个字符 \(i\)。对于单字符 \(a\)，就是 \(0\) 与 \(a\) 连无向边；对于 \(a, b\)，就是 \(a, b\) 连无向边，显然。根据总长度是偶数还是奇数，确定走欧拉路径还是欧拉回路。
一个细节问题：从匹配好的状态加两个字符，和它匹配的一定是和他一样的东西，用不到它当且仅当它与 \(0\) 点不连通。那就看一下是否都是重边就好了。
标签：连通,子树,连通性,选讲,SCC,leq,dfs,sat From： https://www.cnblogs.com/caijianhong/p/18332787