首页 > 漂亮的公园
开通博客写题解
头像 小嗷犬
发表于 2023-08-19 22:25:03
考察知识点：树上 DFS、倍增、LCA 设 为颜色 的两个直径端点（即距离最远的两个点）， 为颜色 中的一个点，则点 到颜色 中点的最大距离为 。 可以想象一个点到一条线段的最远距离必然出现在这个点到两个端点的距离中，在此不做严格证明。 进而我们有如下结论： 设 为颜色 的两个直径端点 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 fuzhiji
发表于 2020-06-03 00:42:24
假设节点颜色为 ,对于求颜色 在树上距离最大的两点，我们需要先找出树上颜色为 的距离最大的两点，找出树上颜色为 的距离最大的两点，然后枚举求不同颜色的两点距离，得到的最大值就是 的最远距离。 所以，我们只需要预处理出所有颜色的最远两点，然后计算的时候用LCA求距离即可。 当然，颜色可能很多，多达 种 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 好运莲莲_
发表于 2020-06-04 15:38:56
牛客—— 漂亮的公园 （离散化+LCA+结论） 原题链接 题意： 给定一棵树，每个节点都对应有一个颜色，问询问的两个颜色之间的最大距离（可两个颜色可以相同也可以不同）。 思路： 首先要知道一个结论是对于同一种颜色的直径端点a,b,另一个点c到达这种颜色的最大值，一定是dis(a,c)和dis（b,c 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”