P1399 [NOI2013] 快餐店

· · 题解

前言：感谢管理员大大百忙中审核题解 QAQ 。

来发数据结构的题解

首先要知道快餐店的选址一定是在这个基环树的直径上（就是最长的一条链）且在其中间位置，那答案就转换为如何求直径长度。

直径有两种情况：

1. 不经过环

我们可以通过 tarjan 求出环上的点，然后用 DP 求出以环内每个点为根子树的最大直径（注意不要经过环）。

2. 经过环

先考虑断环（很套路），枚举断掉哪条边，断环之后就变成求一颗树的直径了。

环上两个点的最短距离还要考虑逆时针还是顺时针太麻烦，将断的环形成的链直接复制一份就可以很好解决这个问题。

假设环长度为 n ，那断掉一条边就等同于在 2n 的序列中选出一段长度为 n 连续的区间。 然后我们要做的就是在区间中选出一个点对，若直径经过两点则其大小为：

dp_i+dp_j+dis_{i,j}

（其中 dp_i 为情况 1 得到的该点可以延伸出去的最长链）。

这样问题就简便多了，但是复杂度还是很高，如何优化呢？

注意到 dis_{i,j} 可以用前缀和表示，即：

dis_{i,j} \gets sum_j-sum_i

然后 直径 (i,j) 变为：

dp_i+dp_j+sum_j-sum_i

对于每个环上点设：

A_i \gets dp_i+sum_i B_i \gets dp_i-sum_i

这样问题变为序列中选一段区间找到两个数使得其 A_i+B_i 最大，这个可以用线段树维护吧！！！

不对，如果最大的 A_i 还有 B_i ，是同一个点呢？那就多维护个最大值位置和次大值呗，也就多打一点点代码然后多带个 \log 吧。

code（不要试图复制哦 qaq ）：


#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+100;
const int inf=1e17；
int n;
int head[N],to[N],ne[N],w[N],tot;
void add(int x,int y,int z){
    ne[++tot]=head[x];
    to[tot]=y,w[tot]=z;
    head[x]=tot;
}
vector<int>g;
vector<int>edge;
int st[N],sum[N];
bool yes,vis[N],in[N];
void find_circle(int u,int fa){
    g.push_back(u),vis[u]=1;
    for(int i=head[u];i;i=ne[i]){
        if(yes) return;
        int v=to[i];
        if(v==fa) continue;
        if(vis[v]){
            int o;
            do{
                o=g.back(),g.pop_back();
                in[o]=1;
                st[++st[0]]=o;
            }while(o!=v);
            for(int j=2;j<=st[0];j++) sum[j]=sum[j+st[0]]=edge.back(),edge.pop_back();
            sum[1+st[0]]=w[i];
            yes=1;return;
        }
        edge.push_back(w[i]);
        find_circle(v,u);   
        edge.pop_back();
    }
    vis[u]=0,g.pop_back();
}
int dp[N],ans=0;
void dfs(int u,int fa){
    int mx1=0,mx2=0;
    for(int i=head[u];i;i=ne[i]){
        int v=to[i];
        if(v==fa or in[v]) continue;
        dfs(v,u);
        if(dp[v]+w[i]>mx1) mx2=mx1,mx1=dp[v]+w[i];  
        else mx2=max(mx2,dp[v]+w[i]);
    }
    dp[u]=mx1,ans=max(ans,mx1+mx2);
}
void work1(){
    for(int k=1;k<=st[0];k++){
        int u=st[k];
        dfs(u,0);
    }
}
int a[N],b[N];
#define lson o<<1
#define rson o<<1|1
struct tree{
    int l,r,mxa1,mxa2,mxb1,mxb2;//A,B的最大还有次大值
    int posa,posb;//A,B最大值的位置
}t[N];
void pushup(int o){
    if(t[lson].mxa1>t[rson].mxa1) t[o].mxa2=max(t[lson].mxa2,t[rson].mxa1),t[o].mxa1=t[lson].mxa1,t[o].posa=t[lson].posa;
    else t[o].mxa2=max(t[rson].mxa2,t[lson].mxa1),t[o].mxa1=t[rson].mxa1,t[o].posa=t[rson].posa;
    if(t[lson].mxb1>t[rson].mxb1) t[o].mxb2=max(t[lson].mxb2,t[rson].mxb1),t[o].mxb1=t[lson].mxb1,t[o].posb=t[lson].posb;
    else t[o].mxb2=max(t[rson].mxb2,t[lson].mxb1),t[o].mxb1=t[rson].mxb1,t[o].posb=t[rson].posb;
}
void build(int o,int l,int r){
    t[o].l=l,t[o].r=r;
    if(l==r){
        t[o].mxa1=t[o].mxa2=a[l];
        t[o].mxb1=t[o].mxb2=b[l];
        t[o].posa=t[o].posb=l;
        return; 
    }
    int mid=(l+r)>>1;
    build(lson,l,mid),build(rson,mid+1,r);
    pushup(o);
}
int mxa1,mxa2,mxb1,mxb2,posa,posb;
void query(int o,int l,int r){
    if(t[o].l==l and t[o].r==r){
        if(t[o].mxa1>mxa1) mxa2=mxa1,mxa1=t[o].mxa1,posa=t[o].posa;
        else mxa2=max(mxa2,t[o].mxa1);
        if(t[o].mxb1>mxb1) mxb2=mxb1,mxb1=t[o].mxb1,posb=t[o].posb; 
        else mxb2=max(mxb2,t[o].mxb1);
        return;
    }
    int mid=(t[o].l+t[o].r)>>1；
    if(r<=mid) return query(lson,l,r);
    else if(l>mid) return query(rson,l,r);
    else return query(lson,l,mid),query(rson,mid+1,r);
}
void work2(){
    int res=inf；
    for(int i=1;i<=2*st[0];i++) sum[i]+=sum[i-1],a[i]=dp[st[i>st[0]?i-st[0]:i]]-sum[i],b[i]=dp[st[i>st[0]?i-st[0]:i]]+sum[i];
    build(1,1,2*st[0]);
    for(int i=st[0];i<2*st[0];i++){
        mxa1=-inf,mxa2=-inf,mxb1=-inf,mxb2=-inf,posa,posb;
        int l=i-st[0]+1,r=i;
        query(1,l,r);
        if(posa!=posb) res=min(res,mxa1+mxb1);
        else res=min(res,max(mxa1+mxb2,mxa2+mxb1)); //注意情况要考虑全
    }
    ans=max(ans,res);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y,z;scanf("%lld%lld%lld",&x,&y,&z);
        add(x,y,z),add(y,x,z);
    }
    find_circle(1,0);
    work1(),work2();
    double ANS=(double)(ans)/2;
    printf("%.1lf",ANS);
}