学习博客：https://www.cnblogs.com/ywjblog/p/9254997.html
树的直径
给定一棵树，树中每条边都有一个权值，树中两点之间的距离定义为连接两点的路径边权之和。树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链。后者通常也可称为直径，即直径是一个
数值概念，也可代指一条路径
树的直径通常有两种求法，时间复杂度均为O(n)。我们假设树以N个点N-1条边的无向图形式给出，并存储在邻接表中。
第一种是dp求法，在这里我只介绍bfs求法：
两次BFS（DFS）求树的直径
通过两次BFS或者两次DFS也可以求树的直径，并且更容易计算出直径上的具体节点
详细地说，这个做法包含两步：
1.从任意节点出发，通过BFS和DFS对树进行一次遍历，求出与出发点距离最远的节点记为p
2.从节点p出发，通过BFS或DFS再进行一次遍历，求出与p距离最远的节点，记为q。
从p到q的路径就是树的一条直径。因为p一定是直径的一端，否则总能找到一条更长的链，与直径的定义矛盾。显然地脑洞一下即可。p为直径的一端，那么自然的，与p最远的q就是直径的另一端。
在第2步的遍历中，可以记录下来每个点第一次被访问的前驱节点。最后从q递归到p，即可得到直径的具体方案
下面看一道例题：
题目链接：https://ac.nowcoder.com/acm/contest/884/A
链接：https://ac.nowcoder.com/acm/contest/884/A
来源：牛客网
A non-negative integer - the minimal time for persons to meet together.
1≤n≤1051 \leq n \leq 10^51≤n≤105
题目大意：给你一颗树，树中某些结点上有人，问你这些人在全部在一点会面的最小是时间是多少
思路：显然就是求最远的两个关键点之间的距离了
看代码：
#include<iostream> #include<stack> #include<cstdio> #include<vector> #include<queue> #include<cstring> using namespace std; const int maxn=1e5+5; #define lson l,mid,rt<<1 #define rson mid+1,r,rt<<1|1 typedef long long LL; const LL INF=1e18; int cnt=0; int head[maxn],dis[maxn]; int a[maxn]; bool vis[maxn],key[maxn]; queue<int>q; struct E { int to,next; }edge[maxn<<1]; void add(int u,int v) { // cout<<"u:"<<u<<" v:"<<v<<endl; edge[cnt].to=v; edge[cnt].next=head[u]; head[u]=cnt++; } void bfs(int x) { // cout<<"2:"<<vis[2]<<endl; vis[x]=true; dis[x]=0; q.push(x); while(!q.empty()) { int u=q.front();q.pop(); for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(!vis[v]) { dis[v]=dis[u]+1; // cout<<"v:"<<v<<" dis[v]:"<<dis[v]<<endl; vis[v]=true;q.push(v); } } } } int main() { memset(head,-1,sizeof(head)); int N,K; cin>>N>>K; for(int i=1;i<N;i++) { int u,v;cin>>u>>v; add(u,v);add(v,u); } for(int i=1;i<=K;i++) { cin>>a[i];key[a[i]]=true;//标记是否为关键点 } bfs(a[1]);//任取一个关键点 // for(int i=1;i<=N;i++) cout<<dis[i]<<" ";cout<<endl; int ma=dis[a[1]],id=a[1]; for(int i=1;i<=N;i++)//找最远的关键点 { if(key[i]&&dis[i]>ma) { ma=dis[i];id=i; } } // cout<<"id:"<<id<<endl; memset(dis,0,sizeof(dis)); memset(vis,false,sizeof(vis)); bfs(id); // for(int i=1;i<=N;i++) cout<<dis[i]<<" ";cout<<endl; ma=-1; for(int i=1;i<=N;i++) { if(key[i]&&dis[i]>ma) { ma=dis[i]; } } cout<<(ma+1)/2<<endl; return 0; }
原文：https://www.cnblogs.com/caijiaming/p/11257804.html