当前位置: 代码迷 >> 综合 >> POJ 1985 树的直径(最长链)
  详细解决方案

POJ 1985 树的直径(最长链)

热度:44   发布时间:2024-01-13 17:50:14.0

题目大意就是求一棵树上距离最远的两个顶点的距离

说是一棵树是因为之前1984题面上说过

然后据说2631跟此题一样

可以随便选择一个点开始进行bfs或者dfs,从而找到离该点最远的那个点(可以证明,离树上任意一点最远的点一定是树的某条直径的两端点之一;树的直径:树上的最长简单路径)。再从找到的点出发,找到据该点的最远点,那么这两点就确定了树的一条直径,两点间距即为所求距离。

这个用反证法可以论证


#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include &l