题意

给定一颗基环树，设从环上删一条边，任意两点的距离的最大值为\(val\)，求\(val_{min}\)

思路

显然\(val\)有两种来源，一种是以环上某个点为根的子树中选两个点，另一种就是从一颗子树出发到另一颗子树，前者可以\(O(n)\)遍历每颗树得到，对于后者，设：

\(st[i]:\)环上的第\(i\)个点，之后会省略这个数组，请自行理解是点还是序号

\(d[i]:\)以i点为根的子树中离i最远点的距离

\(dis[i]:\)\(st[i+1]\)到\(st[i]\)这条边的长度

假设我们选的点为\(i,j\)，i与j的距离可以用前缀和表示，设\(s[i]\)表示\(i\)顺时针走到1的距离，\(sum\)为环长，再钦定\(i>j\)

假设我们断开了\(k\)与\(k+1\)这条边：

1. \(i,j\leq k\)，它们间的最大距离为\((d[i]+d[j]+s[i]-s[j])\)，我们将\(i\)和\(j\)分开，为\((d[i]+s[i])+(d[j]-s[j])\)

2. \(i,j\geq k+1\)，同上

3. \(j\leq k,i\geq k+1\)，最大距离为\((d[i]+d[j]+sum-s[i]+s[j])\)，同理拆开\((d[i]-s[i])+(d[j]+s[j])+sum\)

从上可以知道只需要知道\((d[i]+s[i])\)和\((d[i]-s[i])\)两个值即可。维护\((d[i]+s[i])\)前缀最大值，\((d[i]-s[i])\)后缀最大值解决第三种情况；前两种情况直接维护最大值即可，这里需要注意\(i\)和\(j\)不重复。于是枚举删边就可以做到\(O(n)\)。

Code

int main(){//  freopen("city.in","r",stdin);//  freopen("city.out","w",stdout);    read(n);    for(int i=1;i<=n;++i)    {        int x,y;ll z;        read(x);read(y);read(z);        add_edge(x,y,z);        add_edge(y,x,z);     }    sc(1,0);    for(int i=1;i<=top;++i) dfs(st[i],0);    for(int i=2;i<=top;++i)        for(int j=head[st[i]];j;j=edge[j].next)            if(edge[j].to==st[i-1])            {                d[i]=edge[j].dis;                //实际上这里的d[i]是上面说的dis[i]                break;            }    for(int i=head[st[1]];i;i=edge[i].next) if(edge[i].to==st[top]) d[1]=edge[i].dis;    for(int i=2;i<=top;++i) s[i]=s[i-1]+d[i];    sum=s[top]+d[1];    ll cur=-INF;    for(int i=1;i<=top;++i)    {        if(i!=1) pre[i]=Max(pre[i-1],cur+dis[st[i]][0]+s[i]);        cur=Max(cur,dis[st[i]][0]-s[i]);        //dis[st[i]][0]为上面说的d[i]    }    cur=-INF;    for(int i=top;i>=1;--i)    {        if(i!=top) suf[i]=Max(suf[i+1],cur+dis[st[i]][0]-s[i]);        cur=Max(cur,dis[st[i]][0]+s[i]);    }    adpremax[0]=-INF;    for(int i=1;i<=top;++i) adpremax[i]=Max(adpremax[i-1],dis[st[i]][0]+s[i]);    misufmax[top+1]=-INF;    for(int i=top;i>=1;--i) misufmax[i]=Max(misufmax[i+1],dis[st[i]][0]-s[i]);    for(int i=1;i