[2016北京集训试题6]网络战争-[最小割树(网络流)+kd-tree+倍增]

Description

A 联邦国有 N 个州，每个州内部都有一个网络系统，有若干条网络线路，连接各个 州内部的城市。 由于 A 国的州与州之间的关系不是太好，每个州都只有首府建立了到别的州的网络。具体来说，每个州的首府都只主动地建立了一条网络线路，连接到距离最近的州的 首府。（欧氏距离。如果有多个，选择标号最小的去连接） B 国探知了 A 国的网络线路分布情况，以及攻陷每条网络线路所需花费的代价，B 国首脑想知道断开 A 国某两个城市之间的网络连接，所需的最少代价。请你计算出来告 诉他。 注：两个城市之间可以有多条网络线路。可能有两个首府的坐标相同。

【输入格式】

第一行有一个正整数 N，表示 A 国州的个数。

接下来 N 个部分，每个部分描述每个州的情况： 第一行两个整数