题目描述

小欧正在扮演一个中世纪的皇帝。地图上有n个城市，其中有m条道路每条道路连接了两个城市。小欧占领了其中一些城市。如果两个城市可以通过若干条道路互相到达，且这些道路经过的城市都是小欧占领的，那么这两个城市之间就可以通过经商获得收益1。请注意，每两个城市之间的收益只会被计算一次。现在，小欧准备占领一个未被占领的城市，使得总收益最大化。你能帮帮她吗?

输入描述

带权并查集

step1.如果直接算当前图上的收益

那么就是计算每个1所连接的城市的连通块的大小(size)的$C_{size}^{2}$

因为1城市连通块之间两两都能联通。所以就是size里选两个点的个数。就是一个连通块内的贡献（答案）