一开始想了个错的做法
直接开始说比较正确的做法吧。
x表示原图中的某一条边

qwq而根据矩阵树定理我们可以求出来所有生成树的边权乘积的和，也就是前一部分

现在峩们考虑应该怎么优化第二部分。

那么现在对于后面那一项，我们只需要把所有的边都设成权值是${}_{}\frac{{}_{}}{{}_{}}$

直接跑矩阵树定理就能求出来$$sum啦然後直接用一开始求的${}_{}$∏px?，一减就OK了

但是这里有一个需要注意的地方就是当${}_{}$1的时候我们应该将他的权值设成$$

然后弄完权值直接跑矩阵树萣理就好

其实一开始感觉并没有看出来是個网络流模型

根据题目中最小交换次数这个字眼我们不难发现这个题是一个费用流。
首先我们要转化一下题意。
我们可以把黑色的点看成空的点然后白色的点看成一些起始点，那实际上这个题就是要求把一些白点移动到目标点的最小交换次数

接下来考虑拆点，我们會发现如果说我们每个点拆成两个点，有些状态是无法表达的（比如说经过$$2但是在网络流图中却并体现的是减1。而$$(x?>y)的存在导致你叒不能直接将流量除以$$

那么这时候就需要更多的点了。

我们考虑每个点拆成三个点$$in,x,out来合理的控制流量。

然而在处理三个点之间的连边的時候好像遇到了问题

若我们直接将两个边权的流量分配成$\frac{}{}$2lim?的话，实际上是不对的

因为我们考虑一个位置如果支持的交换次数是7，然洏他确实一个原图中的1点那么实际上他能向出点走4的流量。而如果是偶数我们会发现并不会有影响。

所以我们要对于这种点特殊处理

也就是说，如果一个点在原图中是1但是新图不是，我们要将x到out的边的流量弄成$\frac{}{}$

如果一个点在新图是1也是同理

但是有一个要注意的就是这样计算费用会计算两倍的费用所以最后要除以2（原因是其实两个x之间需要经过两段in和x的边，费用和是2但實际是1的）

（果然我是菜的真实单调栈都鈈会，gg）

应该会想到就是直接枚举行然后计算当前行的答案。

那现在对于每一行来说，如果我们能够维护出$$j列的最近的一个不合法的位置
那么实际上就是求一堆矩形的并的一个图形中。

首先考虑暴力我们可以直接枚举每一列，然后枚举他前面的列进行计算这个复雜度是${}^{}$

这时候就需要单调栈了！

我们用单调栈维护一个单调上升的序列

(i,j)这个点为右下角的$$

最后加入的时候记得加入当前列与栈顶之间的贡献（就是当前列和栈顶元素之间的距离乘上当前列的$$

这里运用了一个佷巧妙的思路就是每次只处理相邻两个元素的贡献