树的直径，即树上的最长路径，显然，树的直径可以有很多条（考虑一棵菊花）。

接下来我们考虑如何求出一棵树的直径。有很多种O(n)的算法。

算法1：我们任取树中的一个节点x，找出距离它最远的点y，那么点y就是这棵树中一条直径的一个端点。我们再从y出发，找出距离y最远的点就找到了一条直径。这个算法依赖于一个性质：对于树中的任一个点，距离它最远的点一定是树上一条直径的一个端点。

下面给出证明。

考虑这样一棵树，我们假设AB是树的直径，C的最远点为D，那么有AC<CD，a+c<d，因为c>0，所以a<d+c，故有a+b<b+c+d，AB<BD，与假设AB是直径矛盾，故性质得证。

算法2：首先，先将无根树转成有根树，定义F[i]表示从i出发向远离根节点的方向走的最长路径的长度，G[i]表示从i向远离根节点的方向走的次长路径的长度。注意F[i]和G[i]不能沿着i的同一个儿子走。特别地，如果i只有一个儿子，那么G[i]=0。答案为max(F[i]+G[i])。

下面是代码实现。再次感谢Anonymous366提供代码，我也进行了修改，并加了注释。这份代码可以求出带权树中的直径，如果只是一棵普通的树，那么val赋为1即可。

作者：zhanxufeng
来源：CSDN
原文：https://blog.csdn.net/zhanxufeng/article/details/80715185
版权声明：本文为博主原创文章，转载请附上博文链接！

#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20100;
int n,father;
int siz[maxn];//siz保存每个节点的子树大小。
bool vist[maxn];
int CenterOfGravity=0x3f3f3f3f,minsum=-1;//minsum表示切掉重心后最大连通块的大小。
vector<int>G[maxn];
void DFS(int u,int x){//遍历到节点x，x的父亲是u。siz[x]=1;bool flag=true;for(int i=0;i<G[x].size();i++){int v=G[x][i];if(!vist[v]){vist[v]=true;DFS(x,v);//访问子节点。siz[x]+=siz[v];//回溯计算本节点的sizif(siz[v]>n/2) flag=false;//判断节点x是不是重心。}}if(n-siz[x]>n/2) flag=false;//判断节点x是不是重心。if(flag && x<CenterOfGravity) CenterOfGravity=x,father=u;//这里写x<CenterOfGravity是因为本题中要求节点编号最小的重心。
}
void init(){memset(vist,false,sizeof(vist));memset(siz,0,sizeof(siz));minsum=-1;CenterOfGravity=0x3f3f3f3f;for(int i=0;i<maxn;i++) G[i].clear();
}
int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);init();for(int i=1;i<n;i++){int u,v;scanf("%d%d",&u,&v);G[u].push_back(v);G[v].push_back(u);}vist[1]=1;DFS(-1,1);//任意选取节点作为根，根节点的父亲是-1。for(int i=0;i<G[CenterOfGravity].size();i++)if(G[CenterOfGravity][i]==father) minsum=max(minsum,n-siz[CenterOfGravity]);else minsum=max(minsum,siz[G[CenterOfGravity][i]]);printf("%d %d\n",CenterOfGravity,minsum);}return 0;
}