思路:树上三点问题通常都会存在某些性质.这道题要求从c出发依次到达a点和b点,求dist(c,a)+dist(a,b)最大,我们不妨先固定两点最长,再考虑从这两点出发到第三点的位置,枚举第三个点的复杂度是线性的.树上最长距离很显然是一个树的直径模型(带权),我们两次bfs求出树的直径之后,枚举第三个点的位置,统计答案即可.
# include<iostream>
# include<cstring>
# include<algorithm>
# include<queue>
using namespace std;
typedef long long ll;
const int N = 200010,M = 400010;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int h[N],e[M],ne[M],idx;
ll w[M];
bool st[N];
ll dist1[N],dist2[N];
int n,m;
ll maxDis;
int node;
int nodea,nodeb;
void add(int a,int b,int c){
e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}
void bfs(int start,ll dist[]){
memset(st,false,sizeof st);
memset(dist,-INF,sizeof dist);
queue<int> q;
q.push(start);
st[start] = true;
dist[start] = 0;
while(q.size()){
for(int i=q.size();i;i--){
auto u = q.front();
q.pop();
for(int i=h[u];i!=-1;i=ne[i]){
int j = e[i];
if(!st[j]){
dist[j] = dist[u] + w[i];
q.push(j);
st[j] = true;
}
}
}
}
maxDis = -INF,node = 0;
for(int i=1;i<=n;++i){
if(dist[i] > maxDis){
maxDis = dist[i];
node = i;
}
}
}
int main(){
memset(h, -1, sizeof h);
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i){
int a,b;
ll c;
scanf("%d%d%lld",&a,&b,&c);
add(a,b,c),add(b,a,c);
}
// 两次bfs找树的直径
bfs(1,dist1);
nodea = node;
bfs(nodea,dist1);
nodeb = node;
bfs(nodeb,dist2);
ll minv = 0;
for(int i=1;i<=n;++i){
if(i == nodea || i == nodeb) continue;
minv = max(minv,min(dist1[i],dist2[i]));
}
printf("%lld\n",maxDis + minv);
// 从直径的两个端点出发分别跑一遍最长路 找到距离a,b两者的较小距离最大的点
return 0;
}