Chris的父母会遵守以下规则：如果A距离C比B距离C近，那么C的父母先去A家寻找C，如果找不到，C的父母再去B家；反之亦然。
但由于他并不知道A，B，C的具体位置，所以现在他希望你告诉他，最坏情况下Chris的父母要耗费多长时间才能找到Chris？
思路
求出树的直径的端点A、B，在一定存在某个点C，使得 A->B+min(C->A, C->B) 为答案
- A->B为直径（不变）
- C->A, C->A 为题目中的规则（A距离C比B距离C近的话，则优先去A，即在A、B中选最小者)，但又由于是最坏情况，所以还需要跳出最小者中的最大值
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e6+5,inf=0x3f3f3f3f;
int n,m,inq[N];
struct node {
ll u,w;
};
vector<node> g[N];
int spfa(int s, vector<ll>& d) {
memset(inq,false,sizeof inq);
queue<int> q; q.push(s), d[s]=0;
while (!q.empty()) {
int u=q.front();
q.pop(), inq[u]=false;
for (auto& to : g[u]) {
int v=to.u, w=to.w;
if (d[v]>d[u]+w) {
d[v]=d[u]+w;
if (!inq[v]) {
q.push(v);
inq[v]=1;
}
}
}
}
ll mx=0, ans=0;
for (int i=1; i<=n; i++) if (d[i]>mx) {
mx=d[i], ans=i;
}
return ans;
}
int main() {
std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>m;
for (int i=0; i<m; i++) {
int u,v,w; cin>>u>>v>>w;
g[u].push_back({v,w});
g[v].push_back({u,w});
}
vector<ll> d1(n+1,inf*inf), d2(n+1,inf*inf);
int A=spfa(1,d1);
d1=vector<ll>(n+1,inf*inf);
int B=spfa(A,d1); //A->B即直径
spfa(B,d2);
ll zj=*max_element(d1.begin()+1, d1.end()), maxD=0;
for (int C=1; C<=n; C++) {
maxD=max(maxD,min(d1[C],d2[C]));
}
cout<<zj+maxD;
return 0;
}