首页 > [NOIP2015]运输计划
开通博客写题解
头像 savage
发表于 2019-09-01 19:06:11
题目描述 公元 2044 年，人类进入了宇宙纪元。 L 国有 n 个星球，还有 n-1 条双向航道，每条航道建立在两个星球之间，这 n 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 savage
发表于 2019-09-07 16:09:09
算法知识点: LCA，树上差分，二分 复杂度： 解题思路： 二分时间，则原问题变成一个判定性问题：是否可以通过去掉一条边，使所有路径的总长度在 以内。 此时去掉所有长度大于 的路径的最长公共边一定是最优的。 那怎么找出所有公共边呢？我们可以将每条路径上的所有边加 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”