题解 P1399 【[NOI2013]快餐店】
貌似都没人讲清楚将题目从基环树转化为树的推论的证明qaq。我还思考这个思考了好久，最后在本题讨论被提醒后才发现整个思路方向错了X
这里就着重讲下这个推论的证明，以及给出一个不太一样的处理断环后树直径的方法（这个要感谢讨论区的 @C3H5ClO qwq）
解析
转化问题
P.S. 写完后感觉自己讲得有点烂...写得很难理解
如果实在不想看下面这段很长的较严谨证明（甚至推荐别看X），可以考虑看这个简单版本：
我们做出答案点的最短路生成树，发现答案点也是该生成树上到其它点距离的最大值最小的点（对于该生成树的答案），于是可以考虑枚举生成树并求生成树的答案。接着又发现枚举生成树求出的答案值不会小于原图的答案值，于是算法正确性成立
（树的答案应该很好求把，最长路径（直径）除二就行了，这个正确性随便怎么证都可以）
（一个空行后开始正式的证明）
为了说明方便，这里对一些下面会用到的记号或函数先做出定义。
设快餐店最优的位置的集合为
且题目所求的答案即为
我们先证明一个引理：
引理 1. 在
T_s 中寻找一个点s' ，使得s' 到其它结点的在T_s 上的距离的最大值最小，则一定有s'\in S
考虑反证法。若有
接着我们再证明一个引理：
引理 2. 枚举
G 的生成树T ，并在生成树上找一点s' ，使得s' 到其它结点的在T 上的距离的最大值最小，并记将该值记为f(T) ；对于有根树我们用同样的方式定义。则对于所有可能的生成树，有f(T)\geq f(T_s), s\in S
由于 引理 1.，我们实际上有
我们的证明思路其实和刚才差不多。若存在一个生成树
有了上面两个引理，实际上我们就能得出一个推论：
推论 1. 枚举
G 的生成树T ，取最小的f(T) 的值，该值即为题目所求的答案（\max\limits_{v\in V}(dist_G(s, v)) ，s\in S ）
由 引理 1. 和 引理 2. ，该推论立即成立
再转化问题
对于一个基环树，枚举它的生成树显然只用枚举断环上的哪条边
首先我们随便选一条边断掉得到一个链，并把得到的链序列复制一遍，这样在这个复制后序列上滑动一个宽度为
具体来讲，我们随便设环上一个结点为起点，并从它开始按规定方向不重复遍历环上结点，就得到了一个序列
同时在做树 dp 时，我们应该已经对环上每一个点处理出了它只向子树走的最长路径，记为
再来考虑一段路径的贡献，其显然为
而
（这里也可以不复制序列，直接根据环上路径性质分类讨论就行了，还更好理解X。这个做法可以参考其他题解以及 这道题）
滑动窗口维护次大值
由于式子里有两个元素，一个是 “加” 一个是 “减”，所以我们要维护两种值的最大值。但注意到当
设区间从
设 0）、次大值（1）
设 0）、次大值（1）
对于任意窗口，设其左端点为
设
另外如果区间有次大值，则应满足
（其实改成
同时这个方法也可维护滑动窗口的其它可逆/不可逆区间信息（不过必须得可合并）
CODE
预处理上述两个数组只需顺着逆着遍历一遍序列，每隔
但注意更新值、记录值（预处理数组）、清空值的顺序，根据上面定义的开/闭区间等会有一些变化（话说这里的顺序我是直接手模出来的X）
另外由于还需记录值对应的结点编号，因此代码会有一些壮观...不过只要思路看懂了自己应该也能敲出来X（最后我实际打出来也没调多久）
#include <cstdio>
#include <iostream>
#define ll long long
using std::max;
using std::min;
const int MAXN =1e5+50;
/*------------------------------Map------------------------------*/
int n, m;
int first[MAXN], tote;
struct edge{
int net, to, w;
}e[MAXN<<1];
inline void addedge(int u, int v, int w){
++tote;
e[tote].to =v, e[tote].w =w, e[tote].net =first[u];
first[u] =tote;
++tote;
e[tote].to =u, e[tote].w =w, e[tote].net =first[v];
first[v] =tote;
}
/*------------------------------Circle------------------------------*/
int circle/*环上一点，相当于 index*/, lenc/*环长度*/;
int pre[MAXN], net[MAXN], evalpre[MAXN], evalnet[MAXN];
bool vis[MAXN], color[MAXN];
int stk[MAXN], top;
int predfs(int u, int eid/*处理重边环*/){
if((eid&1) == 0)
--eid;
else
++eid;
vis[u] =1;
stk[top++] =u;
for(int l =first[u]; l; l =e[l].net)
if(l != eid){
net[u] =e[l].to;
evalnet[u] =e[l].w;
if(vis[e[l].to])
return e[l].to;
else{
int ret =predfs(e[l].to, l);
if(ret != 0)
return ret;
}
}
--top;
return 0;
}
void getCircle(){
int cir =predfs(1, 0);
circle =cir;
lenc =1;
/*接环并给环染色*/
pre[cir] =stk[top-1];
evalpre[cir] =evalnet[stk[top-1]];
color[cir] =1;
while(stk[top-1] != cir){
++lenc;
pre[stk[top-1]] =stk[top-2];
evalpre[stk[top-1]] =evalnet[stk[top-2]];
color[stk[top-1]] =1;
--top;
}
}
/*------------------------------Dfs------------------------------*/
ll dp1[MAXN], dp2[MAXN];/*从 u 向子树走最大、次大的链*/
ll Anst;
void dfs1(int u, int fa){
for(int l =first[u]; l; l =e[l].net)
if(e[l].to != fa && !color[e[l].to]/*避免走环*/){
dfs1(e[l].to, u);
if(e[l].w+dp1[e[l].to] > dp1[u]){
dp2[u] =dp1[u];
dp1[u] =e[l].w+dp1[e[l].to];
}
else if(e[l].w+dp1[e[l].to] > dp2[u])
dp2[u] =e[l].w+dp1[e[l].to];
}
Anst =max(Anst, dp1[u]+dp2[u]);
}
/*------------------------------滑动窗口------------------------------*/
/*其中 z 代表 x 左且 z<x / 右且 z>=x，最近的下标被 m-1 整除的点，其中 m 为窗口大小*/
/*前两个是 dp+sum，后两个是 dp-sum，第二维代表最大/次大值*/
ll l1[MAXN<<1][2]/*(z, x]*/, r1[MAXN<<1][2]/*[x, z]*/, l2[MAXN<<1][2], r2[MAXN<<1][2];
int idl1[MAXN<<1][2], idr1[MAXN<<1][2], idl2[MAXN<<1][2], idr2[MAXN<<1][2];
/*------------------------------Main------------------------------*/
inline int read(){
int x =0; char c =getchar();
while(c < '0' || c > '9') c =getchar();
while(c >= '0' && c <= '9') x = (x<<3) + (x<<1) + (48^c), c =getchar();
return x;
}
inline void modify(ll &mx, ll & mxs, int &idmx, int &idmxs, const ll &val, const int &idval){
if(val > mx)
mxs =mx, idmxs =idmx, mx =val, idmx =idval;
else if(val > mxs)
mxs =val, idmxs =idval;
}
int main(){
n =read();
for(int i =0; i < n; ++i){
int u =read(), v =read(), w =read();
addedge(u, v ,w);
}
getCircle();
for(int u =circle, flg =0; u != circle || flg == 0; u =net[u]){
if(u == circle)
flg =1;
dfs1(u, 0);
}
ll sum =-evalpre[circle];
/*走两圈，序列大致为：s, ..., t, s, ..., t*/
ll mx1 =0, mx1s =0, mx2 =-0x3f3f3f3f3f3f3f3f, mx2s =-0x3f3f3f3f3f3f3f3f;/*mx 最大，mxs 次大，注意 mx2 可能取负数*/
int idmx1 =-1, idmx1s =-1, idmx2 =-1, idmx2s =-1;
for(int u =circle, flg =0, i =0; u != circle || flg < 2; u =net[u], ++i){
if(u == circle)
++flg;
sum +=evalpre[u];
modify(mx1, mx1s, idmx1, idmx1s, dp1[u]+sum, i);
modify(mx2, mx2s, idmx2, idmx2s, dp1[u]-sum, i);
l1[i][0] =mx1, idl1[i][0] =idmx1, l1[i][1] =mx1s, idl1[i][1] =idmx1s;
l2[i][0] =mx2, idl2[i][0] =idmx2, l2[i][1] =mx2s, idl2[i][1] =idmx2s;
if(i%(lenc-1) == 0)/*开区间，且注意顺序 ( 这里顺序我是靠手模解决的 X )*/
mx1 =mx1s =0, mx2 =mx2s =-0x3f3f3f3f3f3f3f3f,
idmx1 =-1, idmx1s =-1, idmx2 =-1, idmx2s =-1;
}
// sum =-evalnet[pre[circle]];
/*注意 sum 不要清空，以及注意接下来对 sum 的处理*/
mx1 =0, mx1s =0, mx2 =-0x3f3f3f3f3f3f3f3f, mx2s =-0x3f3f3f3f3f3f3f3f;
idmx1 =-1, idmx1s =-1, idmx2 =-1, idmx2s =-1;
for(int u =pre[circle], flg =0, i =2*lenc-1/*注意下标*/; u != pre[circle] || flg < 2; u =pre[u], --i){
if(u == pre[circle])
++flg;
if(i%(lenc-1) == 0)/*闭区间，且注意顺序*/
mx1 =mx1s =0, mx2 =mx2s =-0x3f3f3f3f3f3f3f3f,
idmx1 =-1, idmx1s =-1, idmx2 =-1, idmx2s =-1;
modify(mx1, mx1s, idmx1, idmx1s, dp1[u]+sum, i);
modify(mx2, mx2s, idmx2, idmx2s, dp1[u]-sum, i);
r1[i][0] =mx1, idr1[i][0] =idmx1, r1[i][1] =mx1s, idr1[i][1] =idmx1s;
r2[i][0] =mx2, idr2[i][0] =idmx2, r2[i][1] =mx2s, idr2[i][1] =idmx2s;
sum -=evalpre[u];
}
/*走一圈统计答案, 初始窗口大概是这样的：[s, ..., t], s, ..., t*/
ll Ansc =0x3f3f3f3f3f3f3f3f;
for(int u =circle, flg =0, i =0; u != circle || flg < 1; u =net[u], ++i){
if(u == circle)
++flg;
ll Mx1 =0, Mx1s =0, Mx2 =-0x3f3f3f3f3f3f3f3f, Mx2s =-0x3f3f3f3f3f3f3f3f;
int idMx1 =-1, idMx1s =-1, idMx2 =-1, idMx2s =-1;
modify(Mx1, Mx1s, idMx1, idMx1s, r1[i][0], idr1[i][0]), modify(Mx1, Mx1s, idMx1, idMx1s, r1[i][1], idr1[i][1]);
modify(Mx1, Mx1s, idMx1, idMx1s, l1[i+lenc-1][0], idl1[i+lenc-1][0]), modify(Mx1, Mx1s, idMx1, idMx1s, l1[i+lenc-1][1], idl1[i+lenc-1][1]);
modify(Mx2, Mx2s, idMx2, idMx2s, r2[i][0], idr2[i][0]), modify(Mx2, Mx2s, idMx2, idMx2s, r2[i][1], idr2[i][1]);
modify(Mx2, Mx2s, idMx2, idMx2s, l2[i+lenc-1][0], idl2[i+lenc-1][0]), modify(Mx2, Mx2s, idMx2, idMx2s, l2[i+lenc-1][1], idl2[i+lenc-1][1]);
ll Mx;
if(idMx1 != idMx2)/*如果两种最大值的 id 不同*/
Mx =Mx1+Mx2;
else
Mx =max(Mx1+Mx2s, Mx1s+Mx2);
Ansc =min(Ansc, Mx);
}
printf("%.1lf", max(Anst, Ansc)/2.0);
}