[LOJ10159]旅游规划


传送门

题解

树的直径不止一条,而题目要求我们把所有直径上的点给输出来。

数组名 数组作用
d1 i点到叶子节点的最长距离
d2 i点到叶子节点的次长距离
d3 i点向除子树外的最远距离

就拿样例来说,下面这个图应该很清楚了(红色的是树的直径)

显然,如果一个点满足d1+d2=树的直径或者d1+d3=树的直径,那么这个点肯定是树的直径上的点

代码

发表评论

电子邮件地址不会被公开。 必填项已用*标注