这是本文档旧的修订版！
Codeforces Round #706 (Div. 1)
C. Garden of the Sun
题意
给定一些黑格和一些白格，要求将一些白格转化为黑格，使得所有黑格连通但不出现环路。
题目保证以起始时以每个黑格为中心的 $3\times 3$ 范围内没有其他黑格。
题解
当 $n\equiv 1\bmod 3$ 时，考虑将第 $1,4,7\cdots$ 行染成黑色，然后对第 $3k+2,3k+3$ 行的每列，最多只有一个黑格。
如果第 $3k+2,3k+3$ 行间存在黑格，直接将两行的任意一个黑格所在列全染黑，否则将两行的第一列染黑。易知这样即可完成构造。
当 $n\not\equiv 1\bmod 3$ 时，将 $1,4,7\cdots$ 行换成第 $2,5,8\cdots$ 行处理即可。
D. BFS Trees
题意
给定一个连通图，定义以点 $x$ 为根的 $\text{BFS}$ 树是生成树且树上所有点到 $x$ 的距离等于连通图该点到 $x$ 的距离。
定义 $f(x,y)$ 表示既满足是以点 $x$ 为根的 $\text{BFS}$ 树同时也是以点 $y$ 为根的 $\text{BFS}$ 树的生成树的个数。
题解
首先给出结论：假定 $x,y$ 之间有超过一条最短路径，则 $f(x,y)=0$。
因为对于 $x,y$ 之间最短路上的点 $u$，必有 $\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$，易知树上满足该条件的点仅 $\text{dis}(x,y)+1$ 个。
假如 $x,y$ 之间有超过一条最短路径，则图中满足 $\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,y)$ 的点必然超过 $\text{dis}(x,y)+1$ 个，矛盾。
接下来仅考虑 $x,y$ 之间仅有一条最短路的情况，首先易知生成树一定包含 $x,y$ 之间的最短路。
接下来对除最短路外原图中的每条边 $u\to v$，假如保留该边，则必有 $\text{dis}(x,u)=\text{dis}(x,v)\pm 1,\text{dis}(y,u)=\text{dis}(y,v)\pm 1$。
假如 $\text{dis}(x,u)+\text{dis}(u,y)=\text{dis}(x,v)+\text{dis}(v,y)$，则 $u,v$ 必然在 $x\to y$ 的路径上，矛盾。
于是为每个不在最短路上的结点指定一个父结点即可，答案即为所有点的所有可选父结点的个数的乘积。
设当前结点为 $u$，父结点为 $v$，则父结点应该满足 $\text{dis}(x,u)=\text{dis}(x,v)+1$ 且 $\text{dis}(y,u)=\text{dis}(y,v)+1$。
于是可以 $O(m)$ 计算出每个 $f(x,y)$，总时间复杂度 $O(n^2m)$。
