P4408 [NOI2003] 逃学的小孩
感觉这题只有绿
对于 \(A,B\) 而言，谁远谁近并不重要（两者可以调换），不妨设 \(dis_{A,C}<dis_{B,C}\) ，则答案为 \(MAX(dis_{A,C}+dis_{A,B})\) 。
显然，当 \(AB\) 为直径时答案最大，先两遍 dfs 求一下直径，顺便维护一下直径端点至其余点距离与答案中的 \(dis_{A,B}\) 部分 ：
inline void dfs(int p,int fa){
for(int i=0;i<v[p].size();i++){
int to=v[p][i].to;
if(to==fa)continue;
dis[to]=dis[p]+v[p][i].val;
dfs(to,p);
}
if(dis[p]>dis[far])far=p;
}
inline void dfs_(int p,int fa){
for(int i=0;i<v[p].size();i++){
int to=v[p][i].to;
if(to==fa)continue;
dis_[to]=dis_[p]+v[p][i].val;
dfs_(to,p);
}
}
dis[1]=0;dfs(1,0);A=far;
far=0;dis[A]=0;dfs(A,0);B=far;
ans+=dis[B];
dfs_(B,0);
接下来枚举 \(C\)，求 \(MAX(MIN(dis_{A,C},dis_{B,C}))\) :
for(int i=1;i<=n;i++)num=max(num,min(dis[i],dis_[i]));
\(ans\) 与 \(num\) 两者之和即为答案。