[BZOJ3124/Luogu3304][SDOI2013]直径(树的直径)

发布于 2018-05-27  341 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3124/Luogu3304][SDOI2013]直径(树的直径)

Description

小Q最近学习了一些图论知识。根据课本,有如下定义。树:无回路且连通的无向图,每条边都有正整数的权值来表示其长度。如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)
表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。
直径:一棵树上,最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道,对于给定的一棵树,其直径的长度是多少,以及有多少条边满足所有的直径都经过该边。

Tag

树的直径

解决思路

第一问可以用两次搜索求得。
考虑把第一问求出的直径截出来,这样我们就得到了若干直径中的一条。因为直径的性质保证所有的直径必交于连续一段,所以用两个指针扫。先从左往右扫描,从每一个点$BFS$找到最深的点,设这个点的深度为$deep$,若$deep$与该点右边直径部分的长度相同,则说明我们找到了一条新的直径,从这个点向右都不是必须经过的点了,找到右端点。
对于向左的也是同理,这样我们就确定了重合区间的左右端点。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3124/Luogu3304][SDOI2013]直径(树的直径)


HNCJ OIer