题意：给定N点N边的无向连通图，现在让你在图中找一点作为餐厅，使得最远点距离这点最近。
思路：为了保留整数，我们求最小直径，最后去除2。 直径来源于两部分：
1，在外向树中； 那么就是树的直接，一棵树求直径直接跑一边DP就可以了。（或者两遍BFS吧，麻烦一点而已），假设最大值为ans1。
2，可能通过了环。 一定有环上的边不在直接上，我们枚举这个断边。 那么现在就相当于一个X元环，环上的边有权值，X个点也各有权值，现在枚举每个断边，变成一条带枝桠的链，让你求ans2=min(最长链)。
答案就是二者取max(ans1,ans2)。
对于第二份部分，我们可以通过记录一个前缀和，一个后缀和，一个前缀答案，后缀答案，取得。
而bzoj1791让你求基环树的直径，那就是所有位置取max，通过环的部分可以加倍成链用单调队列搞定。
#include<bits/stdc++.h>
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn],To[maxn],Len[maxn],cnt=;
int r[maxn],vis[maxn],tot;
ll L[maxn],sum[maxn],ans,dp[maxn],p[maxn];
void add(int u,int v,int w)
{
Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; Len[cnt]=w;
}
bool dfs(int u,int f)
{
if(vis[u]==)
{ vis[u]=; r[++tot]=u;L[tot]=Len[f]; return true;} //开始出现环
vis[u]=;
for(int i=Laxt[u];i;i=Next[i]){
if(i==(f^)) continue;
if(dfs(To[i],i)) {
if(vis[u]==) return false; //环遍历完了
else {vis[u]=; r[++tot]=u; L[tot]=Len[f]; return true;}
}
}
return false;
}
void treedp(int u,int f) //得到外向树的直径
{
for(int i=Laxt[u];i;i=Next[i]){
if(i==(f^)||vis[To[i]]==) continue;
treedp(To[i],i);
ans=max(ans,dp[u]+Len[i]+dp[To[i]]);
dp[u]=max(dp[u],dp[To[i]]+Len[i]);
}
}
ll A[maxn],B[maxn],C[maxn],D[maxn];
void solve()
{
ll P=,Mx=;
rep(i,,tot) p[i]=dp[r[i]];
rep(i,,tot){
P+=L[i-];
A[i]=max(A[i-],P+p[i]);
C[i]=max(C[i-],P+p[i]+Mx);
Mx=max(Mx,p[i]-P);
}
P=; Mx=; ll res=C[tot];
for(int i=tot;i>=;i--){
if(i==tot) P=;
else P+=L[i];
B[i]=max(B[i+],P+p[i]);
D[i]=max(D[i+],P+p[i]+Mx);
Mx=max(Mx,p[i]-P);
}
rep(i,,tot-) {
ll tmp=max(max(C[i],D[i+]),A[i]+B[i+]+L[tot]);
res=min(res,tmp);
}
ans=max(ans,res);
}
int main()
{
int N,u,v,w;
scanf("%d",&N);
rep(i,,N) {
scanf("%d%d%d",&u,&v,&w);
add(u,v,w); add(v,u,w);
}
dfs(,);
rep(i,,tot) treedp(r[i],);
solve();
printf("%lld",ans/);
if(ans&) puts(".5");
else puts(".0");
return ;
}