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