想求仙人掌的直径, 结果发现树的直径都没弄清楚 QAQ 先记录几个关于树的直径的结论, 并非都会证. 本文考虑的树, 边上可以带正的权值.
直径的端点的度数等于1
树上任意一点的最远点是某条直径的一个端点
这个结论是两遍BFS/DFS求直径的理论基础.
设(s,t)为一条直径, 从点x出发找最远点y, 则|xy| >= |xs|, |xy| >= |xt|. 假设 y != s 且 y != t. 由于边权为正, 又s,t的度数等于1, 所以y不在路径 x-s 或 x-t 上. 于是, |yt| = |xy| + |xt| >= |xs| + |xt| >= |st|. 根据直径的定义, |yt| <= |st|, 故 |yt| = |st|, (y,t)也是树的一条直径.
所有直径的中点过定点 (该点可能不是树上的结点)
首先, 任意两条直径有交点, 否则可以用它们的端点构造出更长的路径.
设(x,y), (z,w)为两条直径. 如果(z,w)过(x,y)的中点m, 容易证明m也是(z,w)的中点.
设(x,y)的中点为m, 半径为r. 不妨令(z,w)与(x,y)交于(x,m) (不含点m), 则 |zm| + |mw| > |zw|. 然而, |zm| <= r, |mw| <= r, 故 |zm| + |mw| <= 2r = |zw|, 矛盾.
综上所述, 所有直径的中点过定点. (NOIP <树网的核>)
A,B是树上两个点集, A+B中最远点对的端点是A或B中最远点对的端点
设(x,y)是A的最远点对, (z,w)是B的最远点对, 则A+B的最远点对是(x,y), (x,z), (x,w), (y,z), (y,w), (z,w)中的一个.
不会......网上也没找到清晰的证明. 待填.
S是树上某点集, S+{x}的最远点对的端点属于{S中最远点对的端点}+{x}
可以看成上面那条性质的推论.
如果有读者会证最后两条性质希望能教教我 QAQ 嗯, 首先得有读者......