P9841 [ICPC 2021 Nanjing R] Puzzle in Inazuma 题解

比较厉害的题。题目给的操作太过于神秘，考虑用已有的操作构造出更加简单的操作。

初始的操作形如：

选四个点 $a,b,c,d$ 和一个值 $x$，把 $\newcommand{\lra}{\leftrightarrow} a\lra b,a\lra c,a\lra d$ 的权重增加 $x$，把 $\newcommand{\lra}{\leftrightarrow} b\lra c,b\lra d,c\lra d$ 的权重减小 $x$。（后面将其简记为 $\text{Op4}(a,b,c,d)$）

这个操作看起来比较难受，考虑用这个操作搞出一些更简单的操作。

扩展到五个点的情况，用 $\text{Op4}$ 操作搞一些更人类的操作。一个构造方案是：

选五个点 $a,b,c,d,e$ 和一个值 $x$，并依次执行下面的操作：

• $\text{Op4}(c,a,d,e,x)$
• $\text{Op4}(e,a,b,d,x)$
• $\text{Op4}(c,a,b,d,-x)$
• $\text{Op4}(e,a,b,c,-x)$

然后考虑执行这四次操作会发生什么。

最终 $\newcommand{\lra}{\leftrightarrow}a\lra b,a\lra c$ 两条边的边权增加了 $x$，$\newcommand{\lra}{\leftrightarrow}a\lra d,a\lra e$ 两条边的边权减少了 $x$。这里把这个操作记作 $\text{Op5}(a,b,c,d,e,x)$。

看上去还是比较复杂，因此考虑继续利用已有操作来简化操作：

选五个点 $a,b,c,d,e$ 和一个值 $x$，并依次执行下面的操作：

• $\text{Op5}(a,b,c,d,e,x)$
• $\text{Op5}(a,b,d,c,e,x)$

容易发现这个操作其实就是让 $\newcommand{\lra}{\leftrightarrow}a\lra b$ 的边权增加 $2x$，$\newcommand{\lra}{\leftrightarrow}a\lra e$ 的边权减少 $2x$。记这个操作为 $\text{Op}(a,b,c,d,e,x)$。

继续扩展到六个点的情况。

选六个点 $a,b,c,d,e,f$ 和一个值 $x$，并依次执行下面的操作：

• $\text{Op}(a,b,c,d,e,x)$
• $\text{Op}(a,d,e,c,f,x)$

此时这个操作会让 $\newcommand{\lra}{\leftrightarrow}a\lra b$ 的边权增加 $x$，$\newcommand{\lra}{\leftrightarrow}a\lra f$ 的边权减少 $x$。

---

然后观察到不论执行多少次操作，边权的和都不会变。考虑简化题意，用第一个图减去第二个图，问题就变为从一个带权图出发，执行若干次操作最终使得这个图的所有边权均为 $0$。因此容易发现若边权的和不为 $0$，则必然无解。否则必然有解，直接把边权转移过去即可。容易证明该策略满足查询数量的限制。

但是因为这个操作需要用六个点才可以正确执行，所以需要特判 $n\in\lbrace4,5\rbrace$ 的情况。