- 「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 \le b \le 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 (\lfloor\log_2 n\rfloor+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\) 的儿子 \(s_0, t_0\) 的子树中，则从 \(s_0\) 到 \(s\)，\(t_0\) 到 \(t\) 一直选择最大的子树一定是不劣的。类似，\(s_0, t_0\) 取最大和次大的子树也是不劣的。
对于构造答案，我们保留 \(s, t\) 路径上的点，以及路径上的方点邻接的圆点，构造双极定向的拓扑序即可。然后将旁边的点加入对应的圆点即可。