首页 > 漂亮的公园

小嗷犬

发表于 2023-08-19 22:25:03

考察知识点：树上 DFS、倍增、LCA 设为颜色的两个直径端点（即距离最远的两个点），为颜色中的一个点，则点到颜色中点的最大距离为。可以想象一个点到一条线段的最远距离必然出现在这个点到两个端点的距离中，在此不做严格证明。进而我们有如下结论：设为颜色的两个直径端点展开全文

fuzhiji

发表于 2020-06-03 00:42:24

假设节点颜色为 ,对于求颜色在树上距离最大的两点，我们需要先找出树上颜色为的距离最大的两点，找出树上颜色为的距离最大的两点，然后枚举求不同颜色的两点距离，得到的最大值就是的最远距离。所以，我们只需要预处理出所有颜色的最远两点，然后计算的时候用LCA求距离即可。当然，颜色可能很多，多达种展开全文

阿里嘎多懒羊羊桑_

发表于 2020-06-04 15:38:56

牛客—— 漂亮的公园（离散化+LCA+结论）原题链接题意：给定一棵树，每个节点都对应有一个颜色，问询问的两个颜色之间的最大距离（可两个颜色可以相同也可以不同）。思路：首先要知道一个结论是对于同一种颜色的直径端点a,b,另一个点c到达这种颜色的最大值，一定是dis(a,c)和dis（b,c 展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛