题目链接：快餐店
震惊！某ZZ选手此题调了一天竟是因为……>>点击查看
一般碰到这种基环树的题都要先想想树上怎么做。这道题如果是在树上的话……好像求一遍直径就做完了？答案就是直径长度的一半……
然后我们来考虑一下基环树上的情况。假设我们选中了一个位置(u)作为快餐店，那么环上的有一条边是没有用的，也就是说(u)到其它所有点的最短路都不会经过这条边。于是，我们就可以枚举删掉环上每条边，就需要快速统计剩下这棵树的直径。如果这课树的直径没有经过环上的边，那么我们是可以通过预处理环上每棵树的直径来得到的。于是，我们接下来只考虑直径经过换上的边的情况。
为了方便讲述，假设环上的点的编号为(1)到(m)，(1)到(x)的边权和为(w_x)。首先，我们需要预处理环上每个点(u)为根往下的最长链(f_u)。然后，我们其实预处理几个数组即可(这里只考虑前缀)，包括(pre_i)，表示环上只用([1,i])这些点组成的最长的链。由于(pre_i=max{f_u+f_v+w_u-w_v}(u>v))，所以我们还需要维护一下(f_x+w_x)，(f_x-w_x)的前缀最大值，然后每次更新即可。注意为了避免选出了两个重复的点，可以每次使用(f_u+w_u+max{f_v-w_v}(v<u))和(pre_{u-1})来更新(pre_u)。类似的可以对后缀求出对应的数组。
然后，我们在枚举环上断哪条边的时候只需要分三种情况讨论即可。假设我们断了边((u,u+1))，那么假设环上最优的两个点为(i，j(i<j))，那么要么(1 le i < j le u)，要么(u+1 le i < j le m)，还有(1le i le u)且(u+1le j le m)。分别用我们预处理出来的结果算出来，取个(max)就是直径。最后把所有直径的(min)和不过环的直径取个(max)就是最终答案的两倍。
然后我递归的时候函数名打错了……然后就到了另外一个函数里面去了……然后一天就这么过去了(捂脸
你不要说我开头那个链接是在骗你吗……你看这里不是讲了原因么→_→
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);
#define maxn 100010
#define maxm 200010
#define INF (1LL<<60)
using namespace std;
typedef long long llg;
int head[maxn],next[maxm],to[maxm],c[maxm],tt;
int n,m,fa[maxn],dfn[maxn],a[maxn];
llg dep[maxn],ans,f[maxn],b[maxn];
llg su[maxn],pr[maxn],qi[maxn][2],ho[maxn][2];
bool vis[maxn];
int getint(){
int w=0,q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') q=1,c=getchar();
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
void link(int x,int y){
to[++tt]=y;next[tt]=head[x];head[x]=tt;
to[++tt]=x;next[tt]=head[y];head[y]=tt;
c[tt-1]=c[tt]=getint();
}
void work(int rt,int u){
while(u!=fa[rt]){
a[++m]=u; vis[u]=1; u=fa[u];
b[m+1]=dep[a[m]]-dep[u];
}
for(int i=1;i<=m;i++) b[i]+=b[i-1];
}
void dfs(int u){
dfn[u]=++tt;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(v!=fa[u] && !dfn[v]){
dep[v]=dep[u]+c[i];
fa[v]=u,dfs(v);
}
for(int i=head[u],v;v=to[i],i;i=next[i])
if(fa[v]!=u && dfn[v]>dfn[u]) b[1]=c[i],work(u,v);
}
void dp(int u){
vis[u]=1;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(!vis[v]){
dp(v); ans=max(ans,f[u]+f[v]+c[i]);
f[u]=max(f[u],f[v]+c[i]);
}
}
void solve(){
qi[0][0]=ho[m+1][0]=pr[0]=-INF;
qi[0][1]=ho[m+1][1]=su[m+1]=-INF;
for(int i=1,u;u=a[i],i<=m;i++){
qi[i][0]=max(qi[i-1][0],f[u]+b[i]-b[1]);
qi[i][1]=max(qi[i-1][1],f[u]-b[i]+b[1]);
pr[i]=max(pr[i-1],f[u]+b[i]-b[1]+qi[i-1][1]);
}
for(int i=m,u;u=a[i],i>=1;i--){
ho[i][0]=max(ho[i+1][0],f[u]-b[i]+b[m]);
ho[i][1]=max(ho[i+1][1],f[u]+b[i]-b[m]);
su[i]=max(su[i+1],f[u]-b[i]+b[m]+ho[i+1][1]);
}
llg g=pr[m],now=0;
for(int i=1;i<m;i++){
now=b[1]+qi[i][0]+ho[i+1][0];
now=max(now,max(pr[i],su[i+1]));
g=min(g,now);
}
ans=max(ans,g);
}
int main(){
File("a");
n=getint();
for(int i=1;i<=n;i++) link(getint(),getint());
tt=0; dfs(1);
for(int i=1;i<=m;i++) dp(a[i]);
solve();
printf("%.1lf",ans/2.0);
return 0;
}
BZOJ提交网址：BZOJ 3242 快餐店