fuzhiji

分类

题解(19)

/ 注册

全部文章（共2篇）

最短路------LCA+bfs

题意简洁明了，数据级别，直接排除了多源最短路的算法，值得一提的是，十分奇特，一棵树的边是，我们可以将这个图看成一棵树加上100条以内的边的图。先考虑一棵树，如何求两点距离？我们需要前置知识点：LCA（最近公共祖先）红色框框的两个节点u,v，求他们的距离，看他们的深度:depth[u]=4，de...

lca bfs

2020-07-07

5 1366

漂亮的公园——虚树+dp+lca

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

虚树树的直径 lca dp

2020-06-03

2 894