icontofig | 发布于 2019-07-04 14:41:30 | 阅读量 183 | 线段树 DP BFS
发布于 2019-07-04 14:41:30 | 线段树 DP BFS
BZOJ 1999 树网的核[数据加强版] 树的直径+线段树
题解此题原本是NOIP提高组一道压轴,这一改数据感觉可以放省选赛或者CCPC难题里面什么的了 鬼知道为什么我当初做这道题会YY出线段树做法,现在想想我自己都佩服我自己。 嘛写这篇算是权当复习一下思路了。 题目告诉我们最小偏心距是什么了……我们要求的就是选定一个长度不超过s的核(在直径上,也可以是点也可以是边)使得离这个核最远的点离这个核 的距离最小。 首先求直径是很好求的,两遍BFS就搞定了。 但是直径可能会有很多条,那我们就对每一条都要计算。 对于每一条直径,我们的答案一定是由两类值的最大值来组成: 1.非此直径上的点到当前选定的核的距离的最大值。 2.直径的两个端点到当前选定的核的距离的最
继续阅读