Description
给定一个基环树，可以在保证树联通的情况之下要求一个最小直径
\(n\le 2\times10^5\)
Solution
这题目就是会说在环上拆掉一条边之后让环上的直径最小
分为几种情况
先说说怎么求基环树的直径吧
也就是\(IOI2008 \ Islands\)
（啊那个题目的主算法是求基环树直径）
首先对于每个点，用树形 \(DP\) 直径和当前树的根节点到子树内的最长链
具体做法如下（自己手动模拟一下其实很可理解）
inline void prework(int x,int fa,int rt)
{
for(int i=1;i<=n;++i)
{
int t=e[i].to; if(t==fa) continue;
prework(t,x);
mx[rt]=max(mx[rt],d[t]+d[x]+e[i].dis);
d[x]=max(d[x],d[t]+e[i].dis);
}return ;
}
然后是基环树找环的问题，直接 \(dfs\)
（引用 \(@jiqimao\) 的话：\(tarjan\) 找环确实大才小用）
然后我们观察如果一条直径经过基环树的话
用 \(d_x\) 表示子树最长链，\(s_x\) 表示环上从环的启示点到 \(x\) 距离
这个起始点不关键，毕竟最后是要前缀和处理掉的
还要加上环型的套路，断开并复制
所以有\(\max\limits_ {y-x< n}\{s_y-s_x+d_x+d_y\}\)
然后枚举每个 \(x\) 的时候需要考虑的只是变量 \(y\)
然后这东西可以看出来是可以单调维护的
然后找出来环，枚举环上的点，计算 \(s_i-d_i\)，用单调队列维护
找直径这部分就解决了
\(1.\) 原来的直径和基环树无关
那么直接上原来的直径就完事了
（先上个bzoj island的方式来个求基环树直径）
\(2.\) 原来的直径和基环树是有关的
考虑经过环的情况
如果经过的环的较短的一端，那么显然是不成立的（走长的一端就更大）
那么断掉那一端上的一条边才能保证让直径变小
首先做一下这个树形 \(dp\) 求直径
然后是求所有情况之下 \(\max\{d_{i}+d_{j}+dis_{j,i}\}\) 的 最小值
这里分几种情况讨论一下：（我一开始以为用一个一样的单调队列就能解决……）
假设边 \((i,i-1)\)
\(1.\)首先是两个端点都在 \(1\to i-1\) 中或者都在 \(i+1\to tmp\) 中
那么可以直接把式子表示出来然后推一推，发现对于枚举的量，都有一个固定的另一边的量，那么记录一下
\(2.\) 直径分别在两边
接着表示一下式子，就是\(s_{tmp}-s_r+s_l+d_l+d_r\)
还是可以分组用变量记录最大值的
\(ans\) 对于所有情况的取 \(max\) 就好了
所以 \(code\) 就慢慢来吧
Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define For(i,a,b) for(int i=a;i<=b;++i)
namespace yspm{
inline int read()
{
int res=0,f=1; char k;
while(!isdigit(k=getchar())) if(k=='-') f=-1;
while(isdigit(k)) res=res*10+k-'0',k=getchar();
return res*f;
}
const int N=2e5+10;
struct node{
int to,dis,nxt;
}e[N<<1];
int head[N],cnt=1,ans;
inline void add(int u,int v,int w)
{
e[++cnt].dis=w; e[cnt].to=v; e[cnt].nxt=head[u];
return head[u]=cnt,void();
}
deque<int>q ;
int vis[N],n,mx[N],d[N],s[N],g[N],tmp,l0[N],l1[N],r1[N],r0[N];
pair<int,int> h[N<<1];
inline int dfs(int x,int pre)
{
if(vis[x]==1) return x;
vis[x]=1;
for(int i=head[x];i;i=e[i].nxt)
{
if(i==(pre^1)) continue;
int t=e[i].to,ret=dfs(t,i);
if(ret)
{
h[++tmp]=make_pair(x,e[i].dis);
return ret==x?0:ret;
}
}
return 0;
}
inline void get(int x,int fa,int rt)
{
for(int i=head[x];i;i=e[i].nxt)
{
int t=e[i].to; if(t==fa||vis[t]==2) continue;
get(t,x,rt);
mx[rt]=max(mx[rt],d[x]+d[t]+e[i].dis);
ans=max(ans,mx[rt]);
d[x]=max(d[x],d[t]+e[i].dis);
}return ;
}
signed main()
{
n=read();
for(int i=1,u,v,w;i<=n;++i) u=read(),v=read(),w=read(),add(u,v,w),add(v,u,w);
dfs(1,-1); //cout<<tmp<<endl;
for(int i=1;i<=tmp;++i) vis[h[i].first]=2;
for(int i=1;i<=tmp;++i) get(h[i].first,0,h[i].first),ans=max(ans,mx[i]);
For(i,1,tmp) s[i]=s[i-1]+h[i].second;
int ans2=1e18+10,tm=-1e18-10;
l0[0]=l1[0]=r1[tmp+1]=r0[tmp+1]=-1e18-10;
For(i,1,tmp)//维护这里的f[i]+v[i]
{
l0[i]=max(tm+d[h[i].first]+s[i],l0[i-1]);
l1[i]=max(l1[i-1],s[i]+d[h[i].first]);
tm=max(tm,d[h[i].first]-s[i]);
}tm=-1e18-10;
for(int i=tmp;i>=1;--i)
{
r0[i]=max(r0[i+1],tm+d[h[i].first]-s[i]);
r1[i]=max(r1[i+1],s[tmp]-s[i]+d[h[i].first]);
tm=max(tm,d[h[i].first]+s[i]);
}
//For(i,1,tmp) cout<<d[h[i].first]<<" "; cout<<endl;
//For(i,1,tmp) cout<<h[i].first<<" "; cout<<endl;
//For(i,1,tmp) cout<<h[i].first<<" "; cout<<endl;
//For(i,1,tmp) cout<<l0[i-1]<<" "; cout<<endl;
//For(i,1,tmp) cout<<l0[i]<<" "; cout<<endl;
//For(i,1,tmp) cout<<l1[i-1]+r1[i]<<" "; cout<<endl;
For(i,1,tmp) ans2=min(ans2,max(l0[i-1],max(r0[i],l1[i-1]+r1[i])));
cout<<max(ans,ans2)<<endl;
return 0;
}
}
signed main(){return yspm::main();}
总结
首先是树形 \(DP\) 求直径，然后这里的后面分析的部分其实并不算难