右方之火
AsunderSquall
·
·
题解
右方之火
题意
你有一个 n 个点 m 条边的无向连通图，每个点有一个初始权值 a_i 以及一个目标权值 b_i 。现在你可以对这张图进行这样的操作：
- 选择一个整数 c，选一条点数为 3 的链，中间点的 a_i 减 2c ，另外两个点 a_i 各加 c。
问是否可以进行若干次操作使得对于每个点都有 a_i=b_i，输出方案。
题解
那个 k \le 4n 是因为尊重出题人的意见，不把做题重心放在步数上。实际上可以做到 k \le n。
首先将所有 a_i \gets a_i - b_i，如果 \sum a_i \not = 0 就输出 No。
先讲特殊性质做法。
算法一
我会做链！
发现操作的顺序没有任何影响，不妨设操作是 (1,2,3,c_1),(2,3,4,c_2) \cdots (n-2,n-1,n,c_{n-2})
我发现 1 号点只有操作 (1,2,3) 才能对他造成影响，因此一定有 c_1=-a_1。
然后一路递推过去，如果最后 a_{n-1}=a_{n}=0 就输出方案，否则输出 No。
期望得分：5。
------------------
### 算法二
我会做菊花！
考虑这样一个模型：
我们可以通过
```
a[3]+=c,a[1]-=c,a[4]+=c;
a[2]-=c,a[1]+=c,a[4]-=c;
```
实现 `a[2]-=c,a[3]+=c`。
那么我们先将 $a_1$ 清零，然后在儿子内进行传递即可，传递到最后一个一定是 $0$。
考虑到每次操作 $a_1$ 的加减都是偶数，如果 $a_1$ 是奇数，就只能 `No` 了。
$k \le 2n-1$。
结合前面算法期望得分：10。
---------------------
### 算法三
我会做环！
为了方便起见我们设环上的点标号分别为 $1,2,3,\cdots n$。
我们假设进行了 $c_i$ 为进行 $(a_i,a_{i+1},a_{i+2})$ 操作的次数（下标循环）。
我们考虑可以列出一个 $n$ 元，有 $n$ 个方程的方程组：
$2c_1-c_n-c_2=a_1
2c_2-c_1-c_3=a_2
\cdots
2c_{n-1}-c_n-c_{n-2}=a_{n-1}
2c_n-c_{n-1}-c_1=a_n
实际上最后一个方程可以由前面的 n-1 个方程线性变换（全部相加再取相反数）得到，所以实际上是有 n-1 个线性无关的方程。
我们发现如果将 c_1,c_2 \cdots c_n 全部加上一个数，等式一样成立。
因此不妨都加上 -c_n，这样 c_n =0。
暴力存储每个 $c_i= A_i c_1 + B_i$，推到最后一个式子就能列出方程了！
不过，这样为什么不会爆 `long long` 啥的？
稍微推一下可知 $c_k = kc_1 - \sum _{i=1}^{k-1} (k-i )a_{i}$。（用数学归纳法可以证明）
最终我们求 $c_1$ 的式子为 $2c_{n-1}-c_{n-2}=a_{n-1}
即 2(n-1)c_1- 2\sum_{i=1}^{n-2} (n-1-i)a_i - (n-2)c_1 + \sum_{i=1}^{n-3} (n-2-i) a_i =nc_1 -\sum_{i=1}^{n-2} (n-i)a_i = a_{n-1}。
如果不整除当然也是 `No`。
$k \le n-1$。
结合前面算法期望得分：20。
------------------
#### 算法四
我会做树！
如果没有一个度数 $\ge 3$ 的节点就是链的情况。
否则以一个度数 $\ge 3$ 的节点 $rt$ 为根。
我们考虑对这棵树做这样的操作：
设根的深度为 $1$，对于所有根的深度 $>2$ 的点 $x$，都直接通过操作 $(x,fa_x,fa_{fa_x})$ 这条链,使 $a_x$ 变为 $0$，从叶子往根进行操作。
最终剩下的部分就是一个菊花了！
为什么这样是对的后面再讲。
$k \le 2n-1$。
结合前面算法期望得分：30。
#### 算法五
我会暴力！
把所有可能的长度为 $3$ 的链都列出来，一共只有 $O(m^2)$ 条。
列出一大堆方程，再高斯消元！
时间复杂度 $O(m^2n^2)$。
$k\le???$。
结合前面算法期望得分：40。
------
#### 算法六
我会优化暴力！
发现上面 $O(m^2)$ 种操作里面很多是不必要的。
实际上只需要 $O(m)$ 条。
还是以这个为例子：
我们只需要 $(2,1,3),(3,1,4),(4,1,5),(5,1,2)$。
比如 $(2,1,4)$ 可以由 $(2,1,3)+(4,1,5)-(3,1,4)$ 造出来。
时间复杂度 $O(mn^2)
结合前面算法期望得分：50。
#### 算法七
从这个算法开始我们讲点靠谱的。
链和环的靠谱做法上面都已经讲了。
其他情况下，一定有一个点的度数 $\ge3$。
那么我们取一个度数 $\ge3$ 的点为根（不妨设这个点为点 $1$，它的儿子为点 $2,3,4 \cdots$）生成一棵 bfs 树。
然后按照树的做法来做。
如果这个时候树根的值不是偶数怎么办？
我们找一条非树边出来和一条树边进行一次 $c=1$ 的操作然后再试一次？如果全部都不行就输出 `No`？
这样为什么是对的？我们等下证明。
时间复杂度 $O(nm)$。
$k \le 2n$。
结合前面算法期望得分：70。
这里有一个乱搞：进行 2000 次随机一条链进行一次操作 $c=1$ 的操作然后每次 chk，和算法七相差不大，而且也基本上没法卡，就放过去了。
注意把所有可能的根全部拿出来生成一遍 bfs 树试试的做法是错误的。
可以被这组数据卡掉：
```txt
1
4 4
1 0 0 -1
0 0 0 0
1 2
1 3
2 3
1 4
```
这个时候合法的根只有 $1$，而生成的 bfs 树不满足条件。
---------------
### 算法八
显然算法七在树根是奇数的情况，可以转化为整棵树只有一对相邻的点分别是 $-1,1$，其他都是 $0$ 的情况。
现在考虑证明仅用树边无法使整棵树全部变成 $0$。
树是一个二分图，不妨设分成了集合 $S,T$。
每次操作只会让 $S$ 或 $T$ 中的**恰好** $2$ 或 $0$ 个数改变奇偶性。
而相邻点对属于不同集合，无法让 $S$ 和 $T$ 中同时让 $1$ 个数改变奇偶性。
这启发我们判断一张图是不是二分图。
如果是二分图，那么判断一下，$S$ 集合中奇数的个数是不是偶数个，如果不是那么一定是 `No`。否则用上述方法构造一定能够构造出来。
这种情况下无论取哪个作为根得到的树分层得到的二分图都是一样的，因此算法七也是正确的。
如果不是二分图，那么先删去一些边使他变为二分图（注意仍然必须保证联通）。如果 $S$ 集合中奇数的个数不是偶数个，那么取一条删去的边，和一条二分图中的边，使得他们可以连成一条链，操作 $c=1$ 一次，这样就保证了 $S$ 和 $T$ 集合中奇数的个数都是偶数个了，再用上述方法构造即可。
这个时候显然算法七的情况包括了算法八的情况，只不过算法八把枚举的情况省去了。
因此就证明了算法七的正确性并且给出了更优秀的算法八，时间复杂度为 $O(n)$。
$k \le 2n$。
结合以上所有算法可以通过此题。
### 算法九
虽然上述做法已经可以通过此题了，但是如果我们要求 $k \le n$ 怎么办？
注意到我们输出常数瓶颈在菊花，我们考虑怎么把菊花的做法优化一下。
假设以 $rt=cnt+1$ 为根，儿子为 $1,2,3,\cdots cnt$。
我们考虑最终操作如果 $\sum _{i=1}^{cnt} a_i =0$，那么也能保证 $a_{rt}=0$。
然后对于 $i \in [1,cnt-3]$，直接进行操作 $(i,rt,cnt,-a[i])$。
对于 $i = cnt-2$，分两次操作，通过调整使得最后有 $a_{cnt}= a_{cnt-1}$。
最后一次操作把 $a_{cnt}$ 和 $a_{cnt-1}$ 同时清零。
这样 $k \le n$。