冒泡ioa
冒泡ioa

[LOJ10159]旅游规划

http://www.yzoj.fun/upload/image/20180827/20180827090543_13812.png

传送门

题解

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

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

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

http://bubbleioa.top/wp-content/uploads/2018/10/旅游规划.jpg

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

代码

发表评论

textsms
account_circle
email

冒泡ioa

[LOJ10159]旅游规划
传送门 题解 树的直径不止一条,而题目要求我们把所有直径上的点给输出来。 数组名 数组作用 d1 i点到叶子节点的最长距离 d2 i点到叶子节点的次长距离 d3 …
扫描二维码继续阅读
2018-10-07