树上直径小结

By Wine93 2013.10

 

1. 求树的直径 

算法：任选一点u为起点，对树进行DFS(BFS)遍历，找出离u最远的点v
以v为起点，再进行DFS(BFS)遍历，找出离v最远的点w。则v到w的路径长度即为树的直径

原理: 设起点为u,第一次DFS(BFS)找到的终点v一定是树的直径的一个端点

证明：可参考*qi巨巨的证明

   http://www.cnblogs.com/*qi/archive/2012/04/08/2437424.html

  

2. 树的直径应用举例

一.模板题    --POJ 1985 Cow Marathon --POJ 2631 Roads in the Norths 

二 .求一条路径，使该路径外的节点到该路径距离的最大值最小。这条路径即为树的直径(证明较简单)    --POJ 3310 Caterpillar

三.求树上每一点的最长路径:可先搜出树的直径(s-t),再从树的2个端点进行搜索,2个的最大值即为该点的答案(证明较简单) --lightoj 1257 树的直径

四.求从树上任意点出发走k个点总路径和最小   --HDU 4607 Park Visit