本题同NOI2013快餐店。
题意：给出一张无向图，其中有n个点，n条边，（n<=2e5）没有自环和重边。求去掉一条边形成一棵树之后，树的直径的最小值。
题解：首先这个图是一个带环外向树的图。就是一个环，然后以某些环上的点为根可以延伸出一棵树。那么生成树的个数等于环上的边数，题目意思就是快速的求出这些生成树的直径。那么先考虑如果某个生成树的直径在外向树上面，那么可以很容易的DP求出外向树直径。因为外向树上面的边是不能够删除的，因此外向树完整的被包括在任何一个生成树中，所以答案至少是外向树上直径最大值。
继续考虑第二类直径：直径的一部分在还上。那么这个直径可以分成三部分：第一段是某个外向树的高度（外向树最深的点到根的距离），第二段是环上的一段，第三段也是一个外向树的高度。那么我们显然可以通过枚举删掉的边，然后求这样三段的一个最大值得到该树的直径（伪直径，因为去掉了直径完全在外向树上的情况） 然后取最小来得到正确答案，但是复杂度太高。
问题回到环上，既然是带环的问题，通常的思路是，去掉任意一条边，把他变成一个链再做考虑。那么假设我们去掉 x 这个环上的边不做考虑，那么我们得到了一个链，同时这个链每个点有一个权重=外向树的最深deep。那么根据我们上边说的这个伪直径的形状：一个权重+一段弧+一个权重。
假如我们去掉的边就是x，那么这棵树上的伪直径都是完整的呈现在链上：通过一个DP可以求得他们的最大值，扫一遍就行了，因为现在已经破开了环，变成了线性的问题，略去不讲（提示：伪直径 = max（弧长+权重）+ max（权重-弧长）=max（权重+弧长-弧长+权重）=max（权重+两个权重之间的弧长+权重））。
假如去掉的边不是x，讨论伪直径的形态：第一、不包括x，这样的伪直径在链上也是以完整形态表现出来，其实在前边已经算过了，不需要再考虑；第二、包括x：那么这个伪直径分为三部分：一段弧+一个权重、x、一段弧长+一个权重，而且这两个（弧长+权重）分布在x的左右两边，也就是顺时针、逆时针两个方向上。那么我们可以在 *链上* 按照和上边相同的思路做两个DP，处理出从x开始，分别顺时针、逆时针的（弧长+权重）的一组dp值。然后再扫一遍，线性枚举一下答案。同时，其实有第三种：弧长+权重，这个其实可以看作 0权重+弧长+权重，和第二类是一样的。
代码说明：best[] 和 best1[] 是计算 两个方向上的 伪直径的最大值的dp数组。good[] 和good1[]是计算 两个方向上的 （弧长+权重）的dp数组。lastLength=断开环的那条边长。
circleNode[]按顺序记录了环上的点。circleLength[]按顺序记录了环上每条边，和circleNode是一一对应。
Code：
#include<bits/stdc++.h> #define INF 0x3f3f3f3f #define LL long long using namespace std; const int MAX = 200050; struct Edge{ int des;LL length; Edge(int des_,int length_):des(des_),length(length_){} }; vector<Edge>E[MAX]; int n; bool vis[MAX]; bool inCircle[MAX]; int circleNode[MAX]; int circleNum; LL circleLength[MAX]; int father[MAX]; LL father_length[MAX]; LL f[MAX]; void dfs_find(int x,int fa){ vis[x] = true; for (Edge temp:E[x]){ int v = temp.des; int length = temp.length; if (v==fa) continue; if (vis[v]){ if (inCircle[v]){ continue; } int u = x; while (u!=v){ inCircle[u] =true; circleNode[++circleNum] = u; circleLength[circleNum] = father_length[u]; u = father[u]; } inCircle[v] = true; circleNode[++circleNum] = v; circleLength[circleNum] = length; continue; } father[v] = x; father_length[v] = length; dfs_find(v,x); } } LL chain=-1; void dfs_dp(int x,int fa){ for (Edge temp :E[x]){ int v = temp.des; LL length = temp.length; if (v==fa||inCircle[v]){ continue; } dfs_dp(v,x); chain = max(chain,f[x]+f[v]+length); f[x] = max(f[x],f[v]+length); } } LL good[MAX],good1[MAX],best[MAX],best1[MAX]; int main(){ scanf("%d",&n); for (int i=0;i<n;i++){ int u,v,l; scanf("%d%d%d",&u,&v,&l); E[u].push_back(Edge(v,l)); E[v].push_back(Edge(u,l)); } dfs_find(1,0); // cout<<"OK"<<endl; for (int i=1;i<=circleNum;i++){ dfs_dp(circleNode[i],0); } LL sum = 0; LL support =-INF; // cout<<"YES"<<endl; for (int i=1;i<=circleNum;i++){ sum+=circleLength[i-1]; good[i] = max(good[i-1],sum+f[circleNode[i]]); best[i] = max(best[i-1],sum+f[circleNode[i]]+support); support = max(support,f[circleNode[i]]-sum); } sum = -circleLength[circleNum]; support = -INF; for (int i=circleNum;i>=1;i--){ // cout<<i<<endl; sum+=circleLength[i]; good1[i] = max(good1[i+1],sum+f[circleNode[i]]); best1[i] = max(best1[i+1],sum+f[circleNode[i]]+support); support = max(support,f[circleNode[i]]-sum); } // cout<<"YES"<<endl; LL ans = best[circleNum]; int lastLength = circleLength[circleNum]; /* printf("last:%d\n",lastLength); for (int i=1;i<=circleNum;i++){ printf("good[%d]=%d ",i,good[i]); printf("good1[%d]=%d ",i,good1[i]); printf("best[%d]=%d ",i,best[i]); printf("best1[%d]=%d\n",i,best1[i]); } */ for (int i=1;i<circleNum;i++){ LL temp = good[i]+good1[i+1]+lastLength; temp = max(max(best[i],best1[i+1]),temp); ans = min(ans,temp); } ans = max(chain,ans); printf("%I64d\n",ans); return 0; }