考察对于一条 \((u, v)\) 的边能够产生的影响是什么。
分成两边，一边的白色数为 \(w_1\)，黑色数为 \(b_1\)，另一边白色数为 \(w_2\)，黑色数为 \(b_2\)，那么答案明显是 \(\min(w1, b_2) + \min(w_2, b_1)\)。
运用第一个 trick，注意到 \(w_1 + w_2 = n, b_1 + b_2 = n\)，所以有 \(ans = \min(w_1, n - b_1) + \min(n - w_1, b_1)\)，同时加上 \(b_1, w_1\)，得到 \(ans = \min(w_1 + b_1, n) + \min(n, w_1 + b_1) - w_1 - b_1\)，那么相当于 \(2\min(w_1 + b_1, n) - w_1 - b_1\)，这个东西明显是在 \(w_1 + b_1\) 和 \(w_2 + b_2\) 中取最小值，于是单组贡献为 \(\min(w_1 + b_1, w_2 + b_2)\)，这个东西是在环上的最小距离。
运用第二个 trick，发现需要使得一个最小值最大，在满足了最大时考虑最小的限制较为困难，将所有白色点的位置放到对称点上，这样可以将最大更改为最小。
此时发现就是需要在一个环上寻找匹配，使得最小距离之和最小，你发现是链的话我们是会做的，运用第三个 trick，总存在一种断环为链的方式，使得取到最小值，并且如果断的边错误，只会让答案更大。
如果是链的话怎么做呢？运用第四个 trick，考察排序后黑点位置和白点位置依次匹配，这样一定是最优的，但是我们要跑 \(n\) 次，咋办呢？考察这个 trick 的后半部分是转到前缀和上考虑，考虑后发现就是循环移位前缀和数组之和，等价于数轴上寻找一个点，使得其它点到它距离之和最小，那么用一个小 trick，取中位数即可。
最后一步，证明这个上界是可以被取到的，貌似可以循环移位证明取到上界的条件互不冲突，但是我不太会。