题意

就是给你一个环基树，然后要你找出一个点（可以在边上），使得这个点到所有图上的点距离最大值最小

题解

先是有一个结论：这个点肯定是在这“树”上的直径的中点，答案就是这个直径的长度的一半
所以其实我们就是要找一条最长的链
答案出现的情况有两种：
1.不经过环上的任意一条边，然后这个扫一下就可以了
2.要经过环，那么这个怎么算呢？
我们知道，对于一个方案，他肯定不会吧环遍历完的，也就是说至少有1条边不会被用到，我们就尝试枚举这一条边，看一下断掉这条边后的最大值取最小就是答案了。
为什么是最大值最小呢。对于最大值，我们是保证他是一条最长链，然后最小值是因为路径不会舍近求远

给环上的点标号1~k
设pre1[i]表示1~i的树上的所有点到1的最大值，suf1[i]表示i~k的树上的所有点到k的最大值
设pre2[i]表示1~i的任意两棵树之间组成的最长链的最大值，suf2[i]类似，表示的是i~k

这个正着和倒着分别扫一遍就可以求出来，具体看看代码吧。。

然后断开i~i+1的边就是
max(pre1[i]+suf1[i+1]+（1和k之间的边长）,pre2[i],suf2[i+1])

然后最后和不经过环的方案取一个最大值

这里有一个细节要注意一下：
就是说在取ans的时候，顺序是有要求的
下面本该是这么写的：

for (LL u=2;u<=cnt;u++)
{LL tt=0;tt=max(tt,pr2[u-1]);tt=max(tt,suf2[u]);tt=max(tt,pr1[u-1]+suf1[u]+cval[cnt]);ans=min(ans,tt);
}
for (int u=1;u<=n;u++) ans=max(ans,d[u]);

但是一开始我偷懒，写成了下面这种

ans=max(ans,d[1]);
for (LL u=2;u<=cnt;u++)
{LL tt=0;tt=max(tt,pr2[u-1]);tt=max(tt,suf2[u]);tt=max(tt,pr1[u-1]+suf1[u]+cval[cnt]);ans=min(ans,tt);ans=max(ans,d[u]);
}

我调了很久都没有调出来，最后才发现这样是有区别的
如果你在里面取了最大值，可能他的最小值就不见了，就会影响我们的答案
看来我比较菜，搞成了min和max都有交换律。。

CODE：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
using namespace std;
typedef long long LL;
const LL N=100005;
LL n;
struct qq
{LL x,y,c,last;
}e[N*2];LL num,last[N];
void init (LL x,LL y,LL c)
{num++;e[num].x=x;e[num].y=y;e[num].c=c;e[num].last=last[x];last[x]=num;
}
bool vis[N];//是不是在栈里面 
bool in[N];//这个点是不是在环上面 
LL cir[N],cnt;//环 
LL cval[N],c1[N];//这个点在环上面与父亲边的权值
stack<LL> sta;
bool find_cir (LL x,LL fa,LL c)//当前的节点 父亲 与父亲边的值
{if (vis[x]==true)//环{cir[++cnt]=x;in[x]=true;cval[cnt]=c;while (!sta.empty()&&sta.top()!=x){LL x=sta.top();sta.pop();cir[++cnt]=x;cval[cnt]=c1[x];in[x]=true;}return true;}vis[x]=true;sta.push(x);c1[x]=c;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa) continue;if (find_cir(y,x,e[u].c)) return true;}sta.pop();return false;
}
LL dis[N],d[N];//这颗子树里面的最长链 子树里面的最长距离 
LL dfs (LL x,LL fa)
{LL re=0;//子树中两点的最远距离 for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa||in[y]==true)//我们的目的是遍历这个森林 continue;re=max(re,dfs(y,x));LL tmp=dis[y]+e[u].c;re=max(re,dis[x]+tmp);//和之前的链并起来dis[x]=max(dis[x],tmp);}return re;
}
LL pr1[N],pr2[N];
LL suf1[N],suf2[N];
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%lld",&n);for (LL u=1;u<=n;u++){LL x,y,c;scanf("%lld%lld%lld",&x,&y,&c);init(x,y,c);init(y,x,c);}memset(in,false,sizeof(in));memset(vis,false,sizeof(vis));find_cir(1,0,0);//寻找环 cval[0]=cval[cnt];//因为是环嘛for (LL u=1;u<=cnt;u++)//现在这棵数被环分成了很多个森林d[u]=dfs(cir[u],0);LL t1=-cval[0],t2=-cval[0];for (LL u=1;u<=cnt;u++){LL nd=dis[cir[u]];t1=t1+cval[u-1];t2=t2+cval[u-1];pr1[u]=max(pr1[u-1],nd+t1);pr2[u]=max(pr2[u-1],nd+t2);t2=max(t2,nd);}t1=-cval[0],t2=-cval[0];for (LL u=cnt;u>=1;u--){LL nd=dis[cir[u]];t1=t1+cval[u];t2=t2+cval[u];suf1[u]=max(suf1[u+1],nd+t1);suf2[u]=max(suf2[u+1],nd+t2);t2=max(t2,nd);}LL ans=suf2[1];for (LL u=2;u<=cnt;u++){LL tt=0;tt=max(tt,pr2[u-1]);tt=max(tt,suf2[u]);tt=max(tt,pr1[u-1]+suf1[u]+cval[cnt]);ans=min(ans,tt);}for (int u=1;u<=n;u++) ans=max(ans,d[u]);printf("%.1lf\n",(double)ans/2.0);return 0;
}