[USACO2004][poj1985]Cow Marathon(2次bfs求树的直径)

时间:2021-10-01 03:04:38

http://poj.org/problem?id=1985

题意:就是给你一颗树,求树的直径(即问哪两点之间的距离最长)

分析:

1、树形dp:只要考虑根节点和子节点的关系就可以了

2、两次bfs:

  ①任意从一个点u出发bfs,设其能到的最远点为v

  ②从v出发重新bfs,设其能到达的最远点为s

  ③则树的直径就是v->s

证明:

  若能证明从任意一个点出发,bfs到的最远点一定在树的直径的端点上,那么第二次bfs就可以证明一定正确了,下面来证明第一次bfs正确性:

  ①若选择的点u在直径上,那么能到的最远点v一定是树的直径的端点之一

    反证:

      若v不是树的直径的端点,设树的直径的端点为v1,v2

      那么就说明path(u,v)>path(u,v1),path(u,v)>path(u,v2)

      所以path(v1,u)+path(u,v)>path(v1,v2),这说明v1,v2不是树的直径的端点,与题设不符,故"v不是树的直径的端点"不成立

  ②若选择的点u不在直径上,那么能到的最远点v一定是树的直径的端点之一。这个也很好说明,我们知道树的直径一定是经过根节点的(特殊的根节点如果只有一   个孩子那么就连到根节点为止),即可以理解跨过根节点两边。所以我们在第一次从u bfs的时候,中间一定会bfs到直径上的某点,那么接下来就是又回到了①   情况了。

  综上,成立、