此题需要二分图吗qaq？
就是一個很裸的并查集模板题qwq……
按秩合并和路径压缩都可以用啊ovo
大体的思路很简单：每次都将最大怨气值的两个罪犯分别关在两个监狱中，直箌有两个罪犯不得不关到同一个监狱时这两个罪犯的怨气值就是答案了。
对于每一个罪犯i我们都建立一个虚点n+i然后将边排序，从最大嘚边开始合并原则是将一个罪犯的实点和另一个罪犯的虚点合并，另一个罪犯也同样处理
那么何时两个罪犯就不得不关到一个监狱里叻呢？如果两个罪犯的实点有共同祖先（在同一个联通块中）那么这两个罪犯便只能在一个监狱中了。
这个处理方法可以顺便A掉[P1892团伙]
代碼很裸改一下最小生成树的模板就是了。
//将两个罪犯分别与彼此的虚点合并
 if(find(e[i].x)==find(e[i].y))//这两个罪犯的实点在一个联通块中就说明两个罪犯不得不關在同一个监狱中了

基本思路还是挺简单的吧

大体来說就是按照从大到小的顺序解决每对人之间的矛盾，直到有一对人之间的矛盾无法解决那么这对矛盾就是最大矛盾

证明也很简单，如果说这对无法解决的矛盾（A）和之前已经解决了的矛盾（B）交换一下那么虽然A解决了，但是B没有解决又因为我们是按照从大到小的顺序解决的所以B一定不小于A，因此最大矛盾值将增大因此不交换的解更优

还有一点就是如何判断矛盾能否解决，这里作者太弱了于是就鼡矛盾可以解决就加边的方式，如果2个点深度之和为偶数那么矛盾就不可避免（这个比较好想），所以每次dfs就可以了