会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
若火险点数 m≤2，两座瞭望台可直接放在火险点上，答案为 0。
否则先把非火险叶子不断剥掉，得到连接所有火险点的核心树。在核心树上求加权直径端点 a,b 及路径 P。最优的两座瞭望台可以假定都在 P 上。
每个火险点投影到 P 上某点 p，记垂距 h，同一 p 取最大垂距 H(p)。二分答案 D：对每个投影点得到 P 上允许放置瞭望台的区间，用“按右端点排序、贪心放置不超过两个离散点”判定能否覆盖全部区间。二分上界取 ⌈diam/2⌉。
复杂度分析
