地图上的 n个城市，由 n-1条道路连接，且任意两个城市连通。
除 1 城市之外的每个都有 一台计算机，安装软件 城市之外的每个都有 一台计算机，安装软件一个 自己的安装时间。
住在 1 城市的蒟蒻要给这 n-1台计算机装配软件，他可以沿着 n-1条道路 行走，每条道路花费的时间为 1。
蒟蒻在第 0时刻出发，他每走到一个城市就立给该的电脑装软件。
因为蒟蒻急着回家，所以他希望在最快到，因为蒟蒻急着回家，所以他希望在最快到 1 城市的基础上，所有电脑完 城市的基础上，所有电脑完成。
【数据规模和约定】
对于 30%的数据，2对于 60%的数据，2对于 100%的数据，2
注意一定要保证回去时间最小，图又是一颗树，所以每条边一定经过两次，而一旦到达一个点，一定要遍历完当前点的所有子树再返回。
这道题设L[k]为从k开始，按照最优决策遍历完所有k的子树，所有软件完成安装所需的最小时间。s[k]是k的子树大小。
注意到这样一个问题，若当前节点有两种选择，1和2，我们所需要做的决策就是
max(l[1],l[2]+2*s[1]),max(l[1]+2*s[2],l[2])这两个数哪一个小，就选小的决策，其中第一个代表先走1，第二个代表先走2。
假设一个节点有q个子树，我们做出了q个决策，那么显然，交换任意两个相邻的决策顺序不会影响其它决策，然后多做几次，选出一个最优的决策。
我的方法是证明在这q个子树中，第一步要么走l最大的，要么走l次大的。因为不走l最大的的原因是其size过大，而毫无疑问，这个事件对l次大的影响是最大的，所以结论成立。
然后按l排序，for i=2 to n，判断每个和第1个哪个更优，更优的就取走，bas+=2*s[k]，剩下的没被取走的就作为第一个。
PS：这题略卡常，用vector存图会TLE
相关资源：第十三届蓝桥杯大赛软件赛省赛C/C++研究生组试题.pdf_蓝桥杯c++…
声明：本站部分文章及图片源自用户投稿，如本站任何资料有侵权请您尽早请联系jinwei@zod.com.cn进行处理,非常感谢！