hdu 4123 Bob’s Race (树的直径+尺取+rmq)(珍爱生命,远离log)

hdu 4123 题目链接

 

题意:一棵树,定义d[i]为点i到树上某点的最大距离。。。给出若干查询,每个查询一个x,问最多能有多少点满足这些点中,最大的d与最小的d的差小于等于x.要求这些点的编号必须是连续的。

思路:可以三遍bfs处理出所有点的d…

由于不能排序。。。所以就是尺取+rmq….

然而神Tm TLE…..

这复杂度还TLe…

结果最后发现是。。。log运算的常数太大被卡。。。

2016-07-17 23-19-46 的屏幕截图 2016-07-17 23-26-58 的屏幕截图

 

所以做法是先预处理一下。。。嗯。。。。

 

珍爱生命,远离log!

珍爱生命,远离log!

珍爱生命,远离log!

 

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz