题目链接：https://www.luogu.com.cn/problem/P4408
一道关于树的直径的题。
首先明确树的直径的概念：树中所有最短路径距离的最大值。
然后明确用DFS/BFS求树的直径的做法：先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是树的直径。
用反证法对于树的直径的证明：https://blog.csdn.net/forever_dreams/article/details/81051578
那么这道题其实就是一道无根树上树的直径的问题：
如图，首先根据上面的做法，用两次BFS求出树的直径，即AB。
那么其实发现在实际上，问题要求max{AB+BC}(BC<AC)或max{AB+AC}(AC<BC)，那么这两个式子可以合并成求max{AB+min{BC,AC}}。
只要确定了直径的端点A、B，然后再枚举C点，求得最大值即为答案。
AC代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<queue> 5 using namespace std; 6 typedef long long ll; 7 const int maxn=200005; 8 struct node{ 9 ll to,next,val; 10 }edge[maxn<<1]; 11 ll d[maxn],k[maxn],head[maxn],vis[maxn]; 12 int n,m,tot; 13 queue<int> q; 14 void add(int u,int v,int w){ 15 edge[tot].to=v; 16 edge[tot].next=head[u]; 17 edge[tot].val=w; 18 head[u]=tot++; 19 } 20 int BFS(int s){ 21 ll maxd=0,Max; 22 memset(d,0,sizeof(d)); 23 memset(vis,0,sizeof(vis)); 24 while(!q.empty()) q.pop(); 25 q.push(s); vis[s]=1; 26 while(!q.empty()){ 27 int u=q.front(),v; q.pop(); 28 for(int i=head[u];i!=-1;i=edge[i].next){ 29 if(vis[v=edge[i].to]) continue; 30 vis[v]=1; 31 d[v]=d[u]+edge[i].val; 32 q.push(v); 33 if(d[v]>maxd){ 34 maxd=d[v]; 35 Max=v; 36 } 37 } 38 } 39 return Max; 40 } 41 int main(){ 42 memset(head,-1,sizeof(head)); 43 scanf("%d%d",&n,&m); 44 for(int i=1;i<=m;i++){ 45 ll x,y,z; 46 scanf("%lld%lld%lld",&x,&y,&z); 47 add(x,y,z); add(y,x,z); 48 } 49 int l=BFS(1);//A 50 int r=BFS(l);//B 51 ll ans=d[r];//直径长度 52 for(int i=1;i<=n;i++) k[i]=d[i];//k:AC长度 53 BFS(r); 54 ll M=0; 55 for(int i=1;i<=n;i++) M=max(M,min(d[i],k[i]));//枚举C点 d:BC长度 56 printf("%lld ",ans+M); 57 return 0; 58 } 59 //树的直径：从任意一点出发，找一个离它最远的点，再从这个点找离它最远的点，这便是树的直径。