比赛：ARC205 Div.2

若每次操作都选择左上角的进行反转，容易看出存在一种操作顺序，使得每次操作只会减少一个四宫格数量，因此只需二维前缀和，统计有多少个四宫格即可。

无论怎样操作，每个点的黑边度数 $d$ 的奇偶性不会改变。

因此每个点最终黑边度数最大是 $(n-1)-(n-1-d)\bmod 2$，即，答案的上界为 $\frac{1}{2}\left(\sum\limits_{i=1}^{n} (n-1)-(n-1-d_i)\bmod 2\right)$。

如果一个点的白边度数 $\ge 2$，那么这个点一定可以进行一次操作，因此这个答案的上界是可以取到的。

无解情况：

判完无解之后直接贪心操作即可。

自底向上贪心。

维护子树内空置点数，以及匹配数。

按顺序合并子树的时候，

容易证明这是最优的。因为最终树内要么只剩一个空置点，这时候已经达到答案上界了；要么剩下的空置点两两都存在祖先关系，并且除了最底下的空置点可能存在非祖先关系节点外，其他空置点都和树上所有点存在祖先关系。

考虑暴力，就是相当于做 $n$ 遍高维前缀和，复杂度 $O(nV)$。

对于这个动态高维前缀和，发现我们加入一个数的复杂度为 $O(V)$，查询的复杂度为 $O(1)$，非常不平衡。

于是为了平衡复杂度，考虑根号分治。维护 $f(x,y)$ 表示序列中所有值为 $2^{10}x+k$ 的数的乘积，其中 $k\subseteq y$，即 $k\operatorname{OR}y=y$。

这样每次加入一个数复杂度为 $O(\sqrt{V})$，查询复杂度为 $O\sqrt{V}$。总复杂度 $O(n\sqrt{V})$。