洛谷 P4886
首先对于一个点 \(c\)，不难用 \(O(n + m)\) 求出他的答案，顺便求出最长距离机器对应的商品 \(idx\)。
设商品 \(idx\) 的起点、终点为 \(s,t\)，设 \(in_u\) 为节点 \(u\) 在 \(c\) 的哪个儿子的子树中。分两种情况讨论：
- 若 \(in_s \ne in_t\)，那么答案不可能更小了（其他节点对于这个快递不可能更小）。直接返回
- 若 \(in_s = in_t\)，那么只用考虑 \(in_s\) 的子树，递归下去即可。
每次取重心即可做到高度 \(\log n\)，时间复杂度：\(O(n \log n)\)。
和传统的点分治不太一样，传统点分治是时间复杂度是 \(O(点数)\) 的，但是要递归到所有分治中心。这个题比较特别，只是用了一下重心的一个结论。