首页 > 环球旅行
开通博客写题解
头像 Lskkkno1
发表于 2020-04-04 21:31:42
环球旅行 题目描述 给定一棵大小为 的树，让你断一条边，使得树上距离最大值最小。 正解 先求出树直径的两个端点 ，，最后断的边肯定是直径上的边。 考虑枚举这条边，然后快速统计答案。 先可以预处理出直径这一条链，然后求出链上前缀的直径和后缀的直径就可以 统计答案了。 断掉直径上的边后，两边联通块 展开全文
去ta的博客 赞 (4) 回复(3) 收起
头像 sunsetcolors
发表于 2020-04-05 03:46:44
环球旅行 原题地址： https://ac.nowcoder.com/acm/problem/201723 基本题意： 切断树的一条边,将树分为两棵,要让两棵树的最长路径(即直径)中较大的那个最小。 基本思路： 开始我们思考的暴力的解法,首先我们很容易想到肯定是要切断直径的,否则直径一定最 展开全文
去ta的博客 赞 (2) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”