AT_agc071_c [AGC071C] Orientable as Desired 题解

:::info[结论 $1$] 若无向图 $G$ 是一棵树，则一定不存在这样的一个数组 $X$ 满足题目中给出的条件。 :::

:::warning[提示 $1$] 试着给树定根，然后自底向上递归处理度数信息？ :::

::::success[证明结论 $1$] 考虑先给树随便定一个根。此时很显然叶子结点可以满足条件。

:::info[结论 $1.1$] 翻转一个结点 $u$ 子树内所有边以及 $u$ 和其父结点的边的方向不会影响 $u$ 子树内除 $u$ 结点以外的所有点的合法性。 :::

:::warning[提示 $1.1$] 考虑 $u$ 子树内的结点入度和出度会怎么变化？ :::

:::success[证明 $1.1$] 翻转一个结点 $u$ 子树内所有的边后，对于 $u$ 子树内一点 $v$，若满足 $v\neq u$ 则 $v$ 点操作前后一定是恰好交换了入度和出度的值。 :::

而对于非叶子结点的限制，考虑先递归处理其所有子结点 $v$ 的子树条件，使得对于所有 $v$ 都是满足条件的。

考虑先给每个子结点 $v$ 的子树以及 $u\leftarrow v$ 的边随便定向使得 $v$ 子树内所有结点的信息都是合法的。此时若 $u$ 结点不合法，根据结论 $1.1$ 可知此时翻转 $v$ 子树内所有的边以及 $u\leftarrow v$ 的边不会导致 $v$ 子树内任意一个点不再满足度数条件，而这样会导致 $u$ 的入度和出度发生 $\pm 1$ 或 $\mp 1$ 的变化。容易发现必然存在一个调整方案使得 $u$ 满足其度数条件。 ::::

:::info[结论 $2$] 若图 $G$ 不是二分图，则必然存在一个数组 $X$ 满足题目给出的条件。 :::

:::warning[提示 $2$] 试着构造一个特殊的 $X$ 数组？ :::

:::success[证明结论 $2$] 构造 $X_1=X_2=\ldots=X_n=0$。则此时要求一个点的入度或出度中至少有一个为 $0$。

也就是对于一个结点 $u$，要么和其相邻的边全都是从 $u$ 出发的，要么和其相邻的边全都是到达 $u$ 的。

考虑按照这个条件把所有点 $u$ 分为两类点：若 $u$ 点相邻的所有边均从 $u$ 出发，则称其为 $1$ 类点，否则称其为 $2$ 类点。

则根据两类点的定义可知，一条边定向后只可以是从 $1$ 类点连向 $2$ 类点的边，即在原图上只能存在连接$1$ 类点和 $2$ 类点的边，不能存在一条边连接的两个点类别相同。因此若要存在一个定向方案满足条件，则图必须是一张二分图。

因此对非二分图，构造 $X_1=0,X_2=0,\ldots,X_n=0$ 就一定不满足题目中给出的度数条件。 :::

:::warning[提示 $3$] 是否只需要研究一类特殊的 $X$ 数组就可以正确求解问题？ :::

:::info[结论 $3$] 只需要研究形如 $X_i=k,X_j=0(\forall j,j\neq i)$ 的数组 $X$ 即可。 :::

:::::success[证明结论 $3$] 先考虑若一个序列 $X$ 中只有一个位置 $X_i$ 的值可以不为 $0$，定向后得到的有向图会形如什么样。容易想到这张图除了 $i$ 结点以外，每个结点要么和其相邻的所有边都从她出发，要么和其相邻的所有点都连向她。

::::warning[提示 $3.1$] 如果翻转树上两个点 $u,v$ 的简单路径上所有边的方向，那么点度数的信息会发生怎样的变化？ ::::

::::success[提示 $3.1$ 的答案] 容易发现若 $u$ 到 $v$ 路径上的点按照顺序可以写作为 $u,x_1,x_2,\ldots,x_p,v$，则 $x_1,x_2,\ldots,x_p$ 点的入度和出度都不会发生变化。而 $u,v$ 两点的入度要么增加 $1$ 要么减少 $1$，出度则刚好相反。 ::::

考虑对于一个不合法的序列 $X$，记位置 $v_1,v_2,\ldots,v_k$ 满足 $X_{v_i}\neq 0$，则考虑每次选择两个非零点 $v_i,v_j$ 然后通过提示 $3.1$ 中给出的操作把 $v_i$ 上度数不为 $0$ 的部分转移到 $v_j$ 上即可。且因为这个转移操作只需要把 $i\to j$ 路径上所有边的方向翻转，因此设得到的新序列 $Y$，则 $X$ 不合法的充要条件即为 $Y$ 不合法，反之同理。 :::::

（这里只讨论 $G$ 是二分图且不是树的情况）此时特判掉 $X$ 序列全 $0$ 的特殊情况，则对于给定的图 $G$，考虑固定 $p$ 点，满足 $X_p\neq 0$。此时考虑在图 $G$ 中删除 $p$ 点以及所有一端为 $p$ 点的边，则此时：

:::info[结论 $4$] 二分图删除一个结点和该结点相邻的边后，得到的新图仍然是一张二分图。 :::

:::info[结论 $5$] 若一张二分图中所有结点对应的 $X$ 值都为 $0$，则确定一个点的入度为 $0$ / 出度为 $0$ 后，一定可以确定整个连通块内每个点入度为 $0$ / 出度为 $0$。 :::

:::success[证明结论 $5$] 确定二分图连通块内一个点入度为 $0$ / 出度为 $0$ 后，一定可以通过二分图染色的方式，使得同色的点一定同时满足入度为 $0$ / 出度为 $0$。而二分图染色确定一个点的颜色后一定可以唯一确定该点所在连通块内其余点的颜色。因此此时染色方案一定唯一，可以唯一确定。 :::

:::info[结论 $6$] $p$ 点向同一个连通块内连的边的方向一定全部相同，即：要么全都是从 $p$ 出发，要么全都是连向 $p$ 点。 :::

:::success[证明结论 $6$] 考虑到二分图删掉若干点后仍然会得到一个二分图，而且二分图一定不存在任何奇环，而除了 $p$ 点以外的所有点都要么全是从 $p$ 出发的边，要么边全都连向 $p$ 点。考虑到前面提到过二分图染色后颜色相同的点必须全都是从 $p$ 点出发的边或者全都是连向 $p$ 点的边，因此 $p$ 点向同一个连通块内连的边的方向必然全都相同。 :::

此时考虑记 $p$ 点删除后各个连通块内和 $p$ 点有边相连的点的数量分别为 $a_1,a_2,\ldots,a_m$，则问题可以被转化为可重集合 $\lbrace a_1,a_2,\ldots,a_m\rbrace$ 中是否对于任意一个整数 $v\in[0,\sum a_i]$ 都存在一个子集 $T\subseteq S$ 满足 $\sum\limits_{i\in T}i=v$。此时考虑 P15253 Raining Mex 的经典结论：

:::info[结论 $7$] 可重集合 $\lbrace a_1,a_2,\ldots,a_m\rbrace$ 中对任意一个整数 $v\in[0,\sum a_i]$ 都存在一个子集 $T\subseteq S$ 满足 $\sum\limits_{i\in T}i=v$，当且仅当把 $a$ 数组内元素升序排序后，对任意 $i$ 都有 $\sum\limits_{j=1}^{i-1}a_j\ge a_i-1$。 :::

::::success[证明结论 $7$] 首先把 $a$ 数组内元素升序排序。此时考虑套路的数学归纳，若当前处理的一段前缀内元素恰好可以凑出 $0\sim x$ 的值，当前要加入的元素值为 $y$，则：若 $x\ge y-1$，则很显然此时可以凑出的元素的值为 $0\sim x+y$，否则此时无法凑出值在 $x+1\sim y-1$ 的元素。但是为什么在某个时刻出现无法凑出的值，后面就再也无法凑出这些值了呢？

:::info[结论 $7.1$] 对于一个升序排列长度为 $n$ 的数组 $a$，若在某个时刻能够凑出的值不是一段连续的区间，则在之后无论怎么插入元素都不会使得能凑出的值是一段连续的区间。 :::

:::success[证明结论 $7.1$] 考虑第一次出现不是一段连续区间前，能凑出值为 $0\sim x$ 的元素，插入了元素 $y$，则必有 $x<y-1$。此时无法凑出值为 $x+1$ 的元素。而在后面加入的所有元素其值都不会小于 $y$，更不会小于 $x+1$，自然也无法凑出值为 $x+1$ 的元素。而显然能凑出元素的上界就是当前所有元素的和，而这个和显然是严格大于 $x+1$ 的。 :::

因此可以证明前面给出的条件就是充要条件。 ::::

于是得到了一个时间复杂度为 $O(n^2)$ 的做法：特判掉二分图和树的情况，然后考虑枚举点 $p$ 作为序列 $X$ 中唯一的非零点，求出删除点 $p$ 后每个连通块和点 $p$ 有边相连的点的数量 $a_i$，排序（这里排序可以使用桶排）后通过结论 $7$ 判断点 $p$ 是否合法即可。显然输出 No 当且仅当对于每个 $p\in [1,n]$，$a_i$ 都可以凑出值在 $0\sim \sum a_i$ 内的元素。

考虑进一步优化该算法的时间复杂度。考虑若一个点 $p$ 不是原图的割点，则原图删掉点 $p$ 和与其相邻的所有边后仍然得到一张二分图，且图仍然是连通的。此时 $p$ 点相邻的所有点，每个点相邻的边的方向都必须是相同的，且做二分图染色后这些和 $p$ 相邻的点的颜色必然是相同的，因此这些点和 $p$ 点之间的边方向必须全部指向 $p$ 或者全部从 $p$ 出发，也就是此时因为 $a_p\neq 0$ 所以只能有 $a_p=\deg(p)$，这个情况是平凡的，无需通过上面的方法讨论。因此直接在图上求出所有的割点然后把这些点依次设为 $p$ 直接枚举和 $p$ 点相邻的每条边即可。总时间复杂度为 $O(n+m\log m)$，可以通过该题。