- 「CF730K」Roads Orientation Problem
- 「CodeChef CUREK」Curing Kingdom
- 「CF1916F」Group Division
- 「IOI2019」景点划分
- 「QOJ 4805」Grammy Sorting
- 「QOJ 8477」Twinning Totem
- 「洛谷 P9394」白鹭兰
「CF730K」Roads Orientation Problem
板子题。
「CodeChef CUREK」Curing Kingdom
考虑所有内部只有一个割点的点双，显然所有这样的点双中只能有最多一个点双初始时没有发到特效药。同时，每个有特效药的点双只需要发一个点就能解决问题。
将没有特效药的那个叶子点双提到根，现在每个叶子都恰好有一个点有特效药，我们只需要将这些叶子的虚树每条边做双极定向即可构造。
写得比较聪明的话大概可以统一成一个过程。
「CF1916F」Group Division
注意到双极定向的拓扑序满足任意前缀和任意后缀均连通。
「IOI2019」景点划分
不妨设 a≤b≤c，我们只需要构造 A,B 分别是连通块，因此这是上一题的加强版。
注意到最多存在一个点双 D 同时与 A,B 相交，因此不妨枚举一个 D，将其提到圆方树的根。
如果 D 最大的子树大小超过了 b+c，则其他子树不可能找出 A。
否则，如果 D 最大的子树大小不小于 b，则容易取出 A,B。
否则，考虑取出 D 内的任意一个双极定向拓扑序，则其第一个子树总大小不小于 a 的前缀一定满足子树总大小小于 a+b，于是后缀大小不小于 c，因此不小于 b。于是也可以取出。
「QOJ 4805」Grammy Sorting
这位更是二合一。
最终的答案显然给出一组 (A,B) 的双极定向，我们只需要先构造一组答案再构造一组操作方案。
构造操作方案是 APC001H。
做法是每一轮 O(n) 解决所有子树内只有一个叶子的点，在每条链维护一个有序的后缀，然后每次如果根结点处的权值属于本轮需要归位的，就移动到对应的后缀，这部分的操作次数不超过需要归位的点数；否则，我们考虑一直把最深的未归位权值往上移动一位，同时会让其祖先的所有未归位权值上移一位，因此这部分的操作次数不超过当前点数。进一步，注意到每一轮至少会使得叶子个数减半，所以总操作次数不超过 n(⌊log2n⌋+1)。
「QOJ 8477」Twinning Totem
容易注意到需要 u 是唯一的割点，或者整个图是一个点双。前者容易拆分成后者。
对于一个点双，我们考虑复制一个 u 作为 u′，那么显然我们存在 (u,u′) 的双极定向。考虑分别取正图和反图的一棵外向生成树即可。
「洛谷 P9394」白鹭兰
k=1 的构造就是双极定向。条件就是点双是一条链。
不妨钦定第一个和最后一个涂黑的点 s,t。考虑 s,t 路径上的方点 u，其不在路径上的子树各自都需要一次删空；考虑路径上的圆点 v，其与其不在路径上的子树的并也需要一次删空。因此它们构成了 k 的下确界。我们需要找到一对 s,t 使得这个下界最小。
设 s,t 的 LCA 为 anc 且分别位于 anc 的儿子 s0,t0 的子树中，则从 s0 到 s，t0 到 t 一直选择最大的子树一定是不劣的。类似，s0,t0 取最大和次大的子树也是不劣的。
对于构造答案，我们保留 s,t 路径上的点，以及路径上的方点邻接的圆点，构造双极定向的拓扑序即可。然后将旁边的点加入对应的圆点即可。