题目大意：
一棵无根树上有三个点A、B、C，求 \(AB+BC\) （要求AB<AC）的最大值。
某篇提解说：由于这是一棵树，它满足非常可爱的性质，就是如果找一个点出去两条路径使它们的合最大，那么一条是直径时一定会存在一种最大的方案。 另一篇题解说：首先找出一条直径，然后枚举除端点外的点C，使得 \(MIN(AC,BC)\) 最大， Ans=树的直径+MIN(AC,BC)+MIN(AC,BC)反正思路都是 树的直径 $ ( A->B )+ min(C->A,C->B) $
......为啥一定是树的直径， I have no idea!
#include#include #include #define LL long long using namespace std;const LL N = 200005;LL n,m,head[N],tot,dis[N],kis[N];struct edge{ LL node,next,data;}e[N<<1];void add(LL x,LL y,LL z){ e[++tot].node=y; e[tot].next=head[x]; e[tot].data=z; head[x]=tot;}void build(LL u,LL f){ for(LL i=head[u];i;i=e[i].next) { LL v=e[i].node; if(v==f) continue; dis[v]=dis[u]+e[i].data; build(v,u); }}int main(){ scanf("%lld%lld",&n,&m); LL x,y,z; for(LL i=1;i<=m;i++) { scanf("%lld%lld%lld",&x,&y,&z); add(x,y,z); add(y,x,z); } build(1,0); LL t=-1,ans=0,k1,k2,ansp=0; for(LL i=1;i<=n;i++) if(dis[i]>t) { t=dis[i]; ans=i; } k1=ans; memset(dis,0,sizeof(dis)); build(ans,0); t=-1,ans=-1; for(LL i=1;i<=n;i++) { kis[i]=dis[i]; if(dis[i]>t) { t=kis[i]; ans=i; } } memset(dis,0,sizeof(dis)); k2=ans;ansp+=t; build(k2,0); ans=-1; for(LL i=1;i<=n;i++) if(i!=k1&&i!=k2) { if(min(dis[i],kis[i])>ans) ans=min(dis[i],kis[i]); } printf("%lld\n",ansp+ans); return 0;}