ABC437G

ABC437G - Colorful Christmas Tree

一道题建了三个新图，算上原树总共四个图 ww

• 给定 $N$ 点树，每个节点初始被染成 012 三种颜色之一。
• 执行以下操作 $N-1$ 次：选择一条当前存在、且两端点颜色不同的边，将其删除，然后将这条边两端点的颜色，按照 0 $\to$ 1 $\to$ 2 $\to$ 0 的循环顺序变为下一种颜色。
• 判断是否存在一种合法的删边顺序，能够把树上的边全部删完。若存在，输出之。

Step.1 转化为匹配

在全过程中，顶点 $v$ 处于颜色 $k$ 时参与删除，这个操作次数确定，记为 $A_{v, k}$。这给定了每个点在特定颜色下需要消耗的额度，因此这本质上是一个匹配问题。

建图：

• 点：将一个点 $v$ 拆成 $A_{v,k}$ 个点 $(v,k)$。
• 边：对于一条边 $u-v$，如果 $(u,k_{1})$ 和 $(v,k_{2})$ 颜色不同，则连边 $(u, k_1)-(v, k_2)$。

在这张新图上，若能做到完美匹配，才可能有解。

Step.2 转化为最大流

注意到树是一张 二分图 （将树按深度的就奇偶性拆分为左部点和右部点），转化后的新图也是二分图， 匹配可以转化为最大流求解。

建图：

• 点：
  • 源点 $s$ 和汇点 $t$。
  • 对于树上的每一个节点 $v$，在网络中拆分成 3 个状态节点 $(v, 1), (v, 2), (v, 3)$。
• 边：
  • 对于所有偶数深度的点 $u$，$s\to(u, k)$，容量 $A_{u, k}$，表示操作次数限制。
  • 对于所有奇数深度的点 $u$，$(v, k)\to t$，容量 $A_{v, k}$，表示操作次数限制。
  • 对于一条边 $u-v$，若 $u$ 为偶数深度，$v$ 为奇数深度，且 $(u,k_{1})$ 和 $(v,k_{2})$ 颜色不同，则 $(u, k_1)\to(v, k_2)$，容量 1，表示合法匹配。

下面证明，原问题有解 $\iff$ 最大流等于 $N-1$。

Step.3 转化的充要性

必要性：如果存在一种合法的删边顺序，那么对应的每次操作都能找到一条从源点到汇点的路径，这时最大流必定等于 $N-1$。

充分性：只需构造一组解。如果能将 时间先后限制 建出一张有向图，并证明它是 DAG，那么其拓扑序就是所需操作序列。

建图：

• 点：原树的 $N-1$ 条边。
• 边：即 依赖关系 。对于原树中的顶点 $v$，其颜色变换是有顺序的，这就给 $v$ 上的所有相连边规定了一个局部时间先后顺序。如果边 $e_A$ 分配到的颜色比 $e_B$ 的颜色更早出现，我们就连一条有向边 $e_A \to e_B$， 表示 $e_A$ 必须在 $e_B$ 之前被删除 。 当然，如果 $e_A$ 分配到的颜色与 $e_B$ 的颜色相同，这个顺序可以任意交换，我们钦定了一个删除顺序并无妨。

下面只需要证明新图无环。

反证，假设存在一个有向环：$e_1 \to e_2 \to e_3 \dots \to e_k \to e_1$。根据我们的建图规则，每一步 $e_i \to e_{i+1}$ 必定发生在这两条边的公共顶点上，记这个公共点为 $v_{i}$。我们将环上的共享顶点按顺序写出来，合并去重，得到一条 walk $v_1, v_2, \dots, v_k, v_1$。

假设 $k=1$，即全部操作发生在一个点 $v_{1}$ 上，这操作当然不可能出现环。

否则，考虑到这是一棵树，如果能找到这样的一个 walk，必然在一个地方掉头了，即存在 $a\to b\to a$ 的片段。这意味着，我们先删除了边 $a-b$，之后又删除了边 $b-a$。

然而，考虑最大流的性质：任何满流方案中，边 $a-b$ 只会被删除恰好 1 次，它在整个时间线上只对应唯一的一个事件，就不可能在依赖环中出现两次。出现了矛盾。

因此假设不成立，新图是 DAG。其拓扑序就是所需操作序列。