P1399 [NOI2013]快餐店

首先我们要知道，如果是树的话，重心的位置一定在一半的直径里那个位置对吧。

所以如果图是一棵树，那么1/2的直径长就是答案了。

（然而这道题没有树的部分分）

看到有n条边就知道是基环树。

既然是基环树，那么我们就应该把环作为重点研究对象。

环就是解题的关键，习惯性地把基环树画成细菌

此时这个基环树的直径有两种情况有经过基环或没有经过基环

没有经过基环的就是环上挂着的每一棵小子树的最大直径了。

有经过基环的怎么求呢？

考虑枚举每个位置把环断开（基环树常见套路）。

对每一个子树求一个最大深度，然后Max(两个子树最大深度加它们在环上的距离)就为直径了。

但我们有很多种断环方案，每一次都求一次复杂度肯定是要上天的。

所以想个办法优化（这里借鉴了ljh2000的方法）

先在1到tot（环长）的地方断开。

pre[]与bck[]分别表示前缀和后缀的 Max[某个子树最大深度+它的前缀（后缀）链长]

bs1[]和bs2[]分别表示前缀和后缀的 Max[某两个子树的最大深度+它们之间的距离]

所以每次从i到i+1的地方断开，答案的求法就很简单了。

1 For(i,1,tot-1){
2    mx1=max(bs1[i],bs2[i+1]);
3    mx2=max(mx1,pre[i]+bck[i+1]+crD[0]);//crD[0]为1与tot之间边的长度
4    Fn=min(Fn,max(mx1,mx2));
5 }

DFS抠环、断环的时候比较繁琐一定要注意细节。

好了上代码（作为一道黑题，并没有很难，千万不要被标签吓倒）

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 #include<algorithm>
  6 #include<cmath>
  7 
  8 #define For(i,a,b) for(register int i=a;i<=b;++i)
  9 #define Dwn(i,a,b) for(register int i=a;i>=b;--i)
 10 #define Pn putchar('
')
 11 #define Re register
 12 #define Db double
 13 
 14 using namespace std;
 15 
 16 const int N=1e5+5;
 17 
 18 int head[N],nxt[N*2],v[N*2],cnt=1;
 19 Db w[N*2],dia[N],z,dmx[N],Fn;
 20 int n,m,x,y;
 21 inline void read(int &v){
 22     v=0;
 23     char c=getchar();
 24     while(c<'0'||c>'9')c=getchar();
 25     while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
 26 }
 27 inline void read(Db &v){
 28     v=0;
 29     char c=getchar();
 30     while(c<'0'||c>'9')c=getchar();
 31     while(c>='0'&&c<='9')v=v*10+c-'0',c=getchar();
 32 }
 33 void add(int ux,int vx,Db wx){
 34     nxt[++cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx; w[cnt]=wx;
 35     nxt[++cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux; w[cnt]=wx;
 36 }
 37 
 38 int tot=0,top=0,st[N],cr[N*2],vis[N],suc=0,fc[N];
 39 Db crD[N*2],stD[N];
 40 void dfsCir(int x,int fa){
 41     vis[x]=1;
 42     if(x==1)st[++top]=x,stD[top]=0;
 43     for(Re int i=head[x];i;i=nxt[i]){
 44         int vv=v[i]; if(vv==fa)continue;
 45         if(!vis[vv]){
 46             st[++top]=vv; stD[top]=w[i];
 47             dfsCir(vv,x);
 48         }else{
 49             suc=1;
 50             while(st[top]!=vv){
 51                 fc[st[top]]=1;
 52                 cr[++tot]=st[top];
 53                 crD[tot]=stD[top--];
 54             }
 55             fc[st[top]]=1;
 56             cr[++tot]=st[top];
 57             crD[tot]=w[i];
 58             return;
 59         }
 60         if(suc)return;
 61     }
 62     top--;
 63 }
 64 int pos;
 65 Db mxD;
 66 void dfsTrD(int x,Db dix,int fa){
 67     if(dix>mxD)mxD=dix,pos=x;
 68     for(Re int i=head[x];i;i=nxt[i]){
 69         int vv=v[i];
 70         if(vv==fa||fc[vv])continue;
 71         dfsTrD(vv,dix+w[i],x);
 72     }
 73 }
 74 Db GetTrD(int x){
 75     pos=mxD=0;
 76     dfsTrD(x,0,0);
 77     mxD=0;
 78     dfsTrD(pos,0,0);
 79     return mxD;
 80 }
 81 
 82 Db pre[N],bck[N],bs1[N],bs2[N],Ds=0; 
 83 void DP(){
 84     Ds=mxD=0;
 85      For(i,1,tot){
 86          pre[i]=max(pre[i-1],dmx[cr[i]]+Ds);
 87          if(i>=2)bs1[i]=max(bs1[i-1],mxD+Ds+dmx[cr[i]]);
 88          mxD=max(mxD,dmx[cr[i]]-Ds);
 89          Ds+=crD[i];
 90     }
 91     Ds=mxD=0;
 92     crD[0]=crD[tot];
 93     Dwn(i,tot,1){
 94         bck[i]=max(bck[i+1],dmx[cr[i]]+Ds);
 95         if(i<=tot-1)bs2[i]=max(bs2[i+1],mxD+Ds+dmx[cr[i]]);
 96         mxD=max(mxD,dmx[cr[i]]-Ds);
 97         Ds+=crD[i-1];
 98     }
 99     Fn=bs1[tot];
100     For(i,1,tot-1){
101         Db mx1=max(bs1[i],bs2[i+1]);
102         Db mx2=max(mx1,pre[i]+bck[i+1]+crD[0]);
103         Fn=min(Fn,max(mx1,mx2));
104     }
105 }
106 
107 int main(){
108     //freopen("ex.in","r",stdin);
109 //    freopen("ex.out","w",stdout);
110     read(n); 
111     For(i,1,n){read(x); read(y); read(z); add(x,y,z);}
112     dfsCir(1,0); 
113     For(i,1,tot){
114         fc[cr[i]]=0;
115         dia[cr[i]]=GetTrD(cr[i]);
116         fc[cr[i]]=1;
117     }
118     For(i,1,tot){
119         mxD=0; 
120         dfsTrD(cr[i],0,0);
121         dmx[cr[i]]=mxD;
122     } 
123     DP();
124     For(i,1,tot)Fn=max(Fn,dia[cr[i]]);
125     printf("%.1lf",Fn/2.0);
126     return 0;
127 }
128