5915. 基环树覆盖
时间限制：1000 MS 内存限制：256 MB
题目描述
## 题目描述 The Kingdom of Byteland consists of several cities connected by bidirectional roads. There are castles standing in some of the cities. Byteasar, the King of Byteland is unhappy with his kingdom's defensive power, so he decided to build k additional castles (he can only afford that many). Whenever one of the cities is attacked by the enemy, the army from the nearest castle must come with help. The enemy is smart, so it will always find and attack the city that is the farthest away from its nearest castle. Therefore, the distance from the attacked city to its nearest castle must be as small as possible. Your job is to calculate and return this distance, assuming that you can decide where to build the k additional castles. The cities are built in a specific manner. Each city has a main gate and several other gates. Every gate is connected to another gate by a road. It is possible that two gates of the same city are connected (see example 2). For defensive reasons, every road has exactly one main gate on one of its ends. Please note that every road can be traversed in both directions. The road going out of the main gate of the i-th city leads to the road[i]'th city and is distance[i] miles long. The int[] castles contains the 0-based indices of the cities in which a castle is already built. 拜特兰王国（The Kingdom of Byteland）由若干座城市组成，城市之间通过双向道路相连。部分城市中矗立着城堡。拜特兰国王拜泰萨（Byteasar）对王国的防御能力不满，因此决定再建造k座城堡（他只能承担这个数量）。 每当某座城市遭到敌人袭击时，必须由距离最近的城堡派出军队支援。敌人十分狡猾，总会找到并袭击**距离其最近城堡最远**的那座城市。因此，被袭击城市与其最近城堡之间的距离必须尽可能小。你的任务是计算并返回这个最小化后的距离——假设你可以自主决定k座额外城堡的建造位置。 这些城市的建造方式具有特殊性：每座城市都有一个正门（main gate）和若干个其他城门。每座城门都通过一条道路与另一座城门相连。同一座城市的两座城门之间也可能存在道路连接（见示例2）。出于防御考虑，**每条道路的两端中恰好有一端是某座城市的正门**。请注意，所有道路都可以双向通行。 从第i座城市正门延伸出的道路通往第road[i]座城市，该道路的长度为distance[i]英里。数组castles中存储的是已建有城堡的城市的编号（编号从0开始）。 ## 题目描述 ：给一个个顶点，N条边的无向图，每条边有长度，某些顶点上已经建了城堡，你可以再选择不超过个顶点建城堡。要使每个顶点到最近城堡的距离的最大值最小。 ## 输入格式 Length of road int[] road Length of distance int[] distance Length of castle int[] castle int k ## 输出格式 int ### 样例 ## 输入 ```in1 5 1 2 3 4 0 5 1 1 1 1 1 0 1 ``` ## 输出 ```out1 2 ``` ## 说明 Building the castle in any of the cities results in the maximum distance from a city to a castle being 2. ```in2 3 1 2 0 3 1 2 3 1 2 1 ``` ```out2 1 ``` ```in3 2 0 1 2 1 1 1 ``` ```out3 0 ``` ```in4 10 0 2 0 0 2 2 8 3 8 7 10 10 9 1 8 1 3 7 2 8 1 3 3 4 6 3 ``` ```out4 3 ``` ```in5 2 1 0 2 5 10 0 1 ``` ```out5 5 ``` ## 数据范围 - road will contain between 2 and 50 elements, inclusive (let's call this number n). - road and distance will contain the same number of elements. - Each element of road will be between 0 and n-1, inclusive. - Each element of distance will be between 1 and 10^6, inclusive. - k will be between 1 and n, inclusive. - castle will contain between 0 and n-k elements, inclusive. - Each element of castle will be between 0 and n-1, inclusive. - The elements of castle will be distinct. - It will be possible to build the castles in such a way that you can always reach a castle from each city.