思路 1 换根DP:
- 第一次dfs 预处理出每一个儿子树的 最长距离1 和次长距离2
- 第二次开始换根DP, 本点到其他 点的距离最长 : 分别考虑 一个是父亲上下来的点len3, 一个是兄弟节点, 就是父亲的最长距离len1或者 次长距离len2,
- 当然这道题要 k个人所在的节点才会产生权值
思路2 树上直径:
- 概念: 任意2个点的距离的最长距离
- 如何求: 谁便选一个点然后dfs找到一个最远的距离的点, (这个点就是直径的端点)
- 然后在以这个点来dfs 在找一个点, 这个点就是直径的另一个端点
- 然后 直径/2 就ok
- 为什么是 直径/2的点, 反证法: 因为如果不是这个点, 那么那个点到这个直径的2个端点, 产生的权值就会大于本来应该的那个点产生的权值
- 同理 当然这道题要 k个人所在的节点才会产生权值