很牛的题目啊。 -Alex_Wei
发现这个操作比较复杂但限制较弱,考虑通过考察“不变的量”来刻画操作。
容易发现若为二分图,则初始颜色不同的一定不能移动到一起。
又因为在存在环的图上这个限制很弱/目前较难考虑,所以先考虑树的情况,发现答案存在可能取到的上界,令 \(c_{i, j}\) 为初始颜色为 \(i\) 的 \(j\) 色棋的数量,上界即为 \((c_{0, 1}\cdot c_{1, 0} + c_{0, 0} \cdot c_{1, 1})\cdot max\ w\),而取到这个上界的必要条件是所有相同的 \(ij\) 合并到一起,并处于最大的边的两端,即初始颜色相同的都到一起,这是较弱的条件,容易达成,考虑什么时候不能达成,即初始颜色相同的不能到一起,此时为链。
偶环和非链二分图是一样的。
非二分图性质比非链二分图还要强,此时答案有取得到的上界 = 黑子个数 * 白子个数 * \(max\ w\)。
考虑链,\(\mathcal O(n^3)\) 做法我没看懂为什么必然是 \([p, d_{p}]\),求教qwq