对于树的情况，每条边的匹配次数都是能取到下界的，也就是子树里面狼和羊的个数的差的绝对值。这可以通过简单的贪心来证明。

在仙人掌上的情况类似，每条树边同样能取到下界，所以只需要考虑环上的情况。假设我们去掉环上的一条边，那么又变成了序列上的情况，和树上类似，可以确定每条边的经过次数 $cnt_i$（可能是负的，表示反向经过），然后答案就是 $\sum_{i=1}^n|cnt_i|\cdot w_i$。现在枚举断开的那条边的经过次数，实际上是把 $cnt_i$ 整体加上了一个数，所以相当于要最小化 $\sum_{i=1}^n|cnt_i-x|\cdot w$，只需要找到 $cnt_i$ 的带权中位数即可。

时间复杂度 $O(n\log n)$。