《重生学神有系统》第257章 NOIP中最难的题型

    本届noip的压轴题，一如既往的难度爆表。

    题目:疫情控制。

    （ps :由于题目较长，编辑后添加，不算字数）

    【问题描述】（梗概）:

    有 n 个城市，用 n-1 条路互连，构成了一棵树。

    1 号城市是树中的根节点，现在，根节点上爆发了一种危害性极高的传染病。

    为了不让疫情扩散到边境城市，也就是叶子节点，于是派出医疗队，在一些城市建立检查点。

    目标:从1 号城市到边境城市的每一条路径上，都至少要有一个检查点。

    医疗队可以在有路互连的城市间移动，并在城市中建立检查点。

    一支队伍只能在一个城市建立检查点，边境城市也可以建立检查点，但1 号城市不能建立检查点。

    医疗队移动所需时间，等于道路的长度，单位是小时。

    一个城市可以驻扎多个医疗队，不同的医疗队可以同时移动。

    现在，一些城市中已经驻扎有医疗队。

    求解:最少需要多少个小时，才能控制住疫情。

    【输入数据】:

    第一行，一个整数 n，表示城市个数；

    接下来的 n-1 行，每行 3 个整数:u、v、w，表示从城市 u 到城市 v 有一条长为 w 的道路。

    数据保证输入的是一棵树，且根节点编号为 1。

    下一行，一个整数 m，表示医疗队的个数。

    再下一行，有 m 个整数，分别表示 m个医疗队所驻扎的城市编号，其中任意m≠1。

    【输出格式】:

    只有一个整数，表示控制疫情需要的最少时间，如果无法控制疫情则输出-1。

    题目后面，还给出了一些输入输出的样例和解释。

    最后，是这道题的数据范围。

    对于 20%的数据，2≤ n≤ 10；

    对于 40%的数据，2 ≤n≤50， w大于0小于 105；

    对于 60%的数据，2 ≤ n≤1000，w大于0小于 106；

    对于 80%的数据，2 ≤ n≤10，000；

    对于 100%的数据，2≤m≤n≤50，000，w大于0小于 109。

    这很可能是最近几年来最难的一道题，思考难度超大。

    即使在noip历史上，也足可以排进难度榜三甲。

    而且有个很恶心的条件，不能停留在根节点。

    写代码的时候，一不小心就容易出错。

    至于解题思路……

    江寒全力开动脑筋，花了10分钟时间，才理顺了过来。

    医疗队可以同时移动，说明需要的总时间，取决于移动距离最长的医疗队。

    根据题意，需要最小化最大值。

    不能用模拟的办法，容易超过时限。

    江寒看懂题意后，第一个念头就是二分答案。

    求最大化最小值，最小化最大值，一般都可用二分答案。

    然后，可以在二分之后，使用贪心策略，将所有的医疗队尽可能上提。

    但是，数据范围太大了，直接一个个“上提”，肯定会导致tle（超时）。

    所以必须优化一下。

    这种”往上提“的问题，一般可以用倍增法来优化。

    具体到这道题里，可以用dfs（depth first search，深度优先搜索）算法，将需要用到的数值预处理一下，然后再倍增。

    在操作时，要时刻注意，不能把医疗队提升到根节点上……

    所以，这道题要想得高分，二分答案、贪心、倍增三种算法，缺一不可。

    在历届noip提高组复赛中，这道题的难度都是数一数二的了。

    但会者不难。

    对江寒来说，只要有了思路，写代码并不存在任何问题。

    他全力开动脑力，只用了30分钟，就写完了代码，并调试完毕。

    虽然问题顺利解决掉了，不过……

    江寒揉了揉有点发烫的脑门，忍不住叹了口气:“啧，早知道带条红极参过来就好了。”

    noip比赛是允许带饮食的。

    虽然生吃海参、不蘸酱油，可能有点另类和惊世骇俗，可总比享受脑力透支的眩晕感好一些吧

    接下来还有将近1个小时，江寒也没浪费。

    编写代码，生成大量测试数据，对自己要提交的代码，进行了高强度的测试。

    测试结果非常不错，100%的测试数据，都能在时限之内完成。

    随后，江寒仔细检查了一下各种细节，文件名、大小写、头文件引用、输出数据的格式……

    全部弄利索，还差5分钟收卷。

    江寒举手叫来监考教师，再次提前了一小会儿，上传了答卷。

    至此，本届noip对他来说，就基本宣告结束了。

    接下来，回家等着成绩公示即可。

    根据赛组委的安排，大约7天后，选手们就能在官网上查询到自己的分数。

    交完卷，江寒走出大楼，呼吸着初冬的寒风，心情愉快。

    “看你的样子，发挥得还算不错”高俊德第一时间迎上来。

    江寒笑了笑:“也算达到了预期目标吧，所有题都做出来了，自己测试也没发现什么问题。”

    “那就好，这我就心里有底了。”高俊德十分欣慰。

    这还真不是盲目乐观。

    在他看来，以江寒的惊人实力，就算发挥失常，也基本上一等奖稳稳的。

    江寒和老高聊了几句。

    听说一会儿几名学生要去放松一下，老高也没横拦竖挡。

    不过……

    “去玩可以，我得一路跟着。”老高笑眯眯地说。

    江寒洒然一笑:“那当然欢迎的了。”

    随后就拿出手机，给夏雨菲打了过去。

    很快电话接通。

    “在哪呢”江寒问。

    “陪苗姐、浩哥去谈了个合同，然后在