题目（bzoj）
（bzoj的样例有问题......）
题目（洛谷）
来说说这题吧。
首先，读完题就应该明白，这道题如果原图只是一棵树的话，就只需要求其直径再/2，完毕。然而原图是一个基环树，而处理基环树都是断环操作。
那么，暴力的做法就出来了：
枚举环上的边，将其断开，求一遍直径，在这里面找个最小的，除以2，完毕。
据说这么做期望60分，鼓掌。
然后来说说100分做法吧。
很明显，100分便是在60分的暴力上进行优化，
而这个优化便从断环开始。
首先，这个断环就很有意思，因为60分做法里面要枚举每一条边断开，
而实际上，我们只需要讲环拆成链就行，
也就是像石子合并这种区间dp题那样去处理环。
这么说有些抽象，总之，断环的操作如下：
1.将环从某个点从1开始编号，然后沿着环走，2，3，4......
2.将这个序列复制一次并放在原序列后面。
比如原序列为1，2，3，4，
这么操作后序列就变为1，2，3，4，1，2，3，4（最后这个4可以不要）
就实现了断环操作，得到了一个序列。
基环树有一个特征：每棵子树的根节点都在环上。
而基环树上的路径也很有意思：要么经过环，要么不经过环。
经过环的话有些麻烦，不过还是比较好理解：
设当前环上某个点i，到以i为根的子树中最大路径长度为d[i]，它到环上1号点的距离为s[i]，
从以i为根的子树到以j为根的子树的路径的最大值为d[i]+d[j]+s[j]-s[i]，
移项，得d[i]-s[i]+d[j]+s[j]，
可以证明这是单调递增的，所以我们设v1=d[i]-s[i], v2=d[j]+s[j]，v=d[i]-s[i]+d[j]+s[j]，
要让v最大，则分别让v1最大和v2最大。
重头戏来了！
怎么快速求v？
线段树啊！
对之前说的序列建一棵线段树，维护3个值，v，v1，v2，
并且以[i,i+1]为一个单点，这样就实现了维护（因为有可能绕开走）
每次查询query(i,i+k-1,root)，（k为环上点的个数，i为区间左边界，i+k-1为区间有边界，root为线段树的根节点编号），取个最小值，完了。
然后是直径不经过环的情况：
很简单，分别对这k个子树求个直径，并取个最大值。
于是这道题就做完了！巨tm爽！
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define readf(f) scanf(
#define eps 1e-18
#define N 200005
using namespace std;
template <class _E> inline void read(_E &e)
{
e=0;bool ck=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')ck=1;ch=getchar();}
while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
if(ck)e=-e;
}
int n,idx,root;
struct edge{
int vk;
ll wk;
int nxt;
}e[N<<1];
int tt,head[N];
int vis[N];
ll d[N<<1],s[N<<1],dis[N];
int h[N];
inline void ad(int u,int v,ll w)
{
e[++tt].vk=v;
e[tt].wk=w;
e[tt].nxt=head[u];
head[u]=tt;
}
bool dfs_huan(int u,int fa)
{
vis[u]=1;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].vk;
if (v==fa) continue;
if (vis[v])
{
h[++idx]=u;
s[idx]=e[i].wk;
vis[v]=0;
return true;
}
bool check=dfs_huan(v,u);
if (check)
{
h[++idx]=u;
s[idx]=s[idx-1]+e[i].wk;
if (vis[u]) return true;
return false;
}
}
return false;
}
ll h_to_son(int u,int fa)
{
ll ret=0;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].vk;
if (v==fa || vis[v]) continue;
ll tmp=h_to_son(v,u);
ret=max(ret,tmp+e[i].wk);
}
return ret;
}
int node,f,c[N];ll deep;
void dfs_dis(int u,int fa)
{
c[++f]=u;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].vk;
if (v==fa || vis[v]) continue;
dis[v]=dis[u]+e[i].wk;
dfs_dis(v,u);
}
}
ll find_son_dist(int x)
{
vis[x]=0;
ll ret;
f=0,dis[x]=0;
deep=node=0;
dfs_dis(x,x);
for (int i=1;i<=f;++i)
if (deep<dis[c[i]]) deep=dis[c[i]],node=c[i];
for (int i=1;i<=f;++i)
dis[c[i]]=llmax;
f=0,dis[node]=0;
dfs_dis(node,node);
node=deep=0;
for (int i=1;i<=f;++i)
if (deep<dis[c[i]]) deep=dis[c[i]],node=c[i];
vis[x]=1;
return deep;
}
struct Segment_tree{
int l,r;
ll v1,v2,v;
}t[N<<2];
int Ls[N<<2],Rs[N<<2],cnt;
inline void up(int id)
{
int ls=Ls[id],rs=Rs[id];
t[id].v1=max(t[ls].v1,t[rs].v1);
t[id].v2=max(t[ls].v2,t[rs].v2);
t[id].v=max(t[ls].v,t[rs].v);
t[id].v=max(t[id].v,t[ls].v1+t[rs].v2);
}
void build(int l,int r,int &id)
{
id=++cnt;
t[id].l=l,t[id].r=r;
if (l+1==r)
{
t[id].v1=d[l]-s[l];
t[id].v2=d[r]+s[r];
t[id].v=t[id].v1+t[id].v2;
return;
}
int mid=(l+r)>>1;
build(l,mid,Ls[id]);
build(mid,r,Rs[id]);
up(id);
}
ll maxn,ans=llmax;
ll query(int l,int r,int id)
{
int L=t[id].l,R=t[id].r;
if (r<=L || l>=R) return 0;
if (l<=L && R<=r)
{
ll tmp;
tmp=max(t[id].v,maxn+t[id].v2);
maxn=max(maxn,t[id].v1);
return tmp;
}
return max(query(l,r,Rs[id]),query(l,r,Ls[id]));
}
int main()
{
read(n);
for (int i=1;i<=n;++i)
{
int uu,vv;ll ww;
read(uu),read(vv),read(ww);
ad(uu,vv,ww),ad(vv,uu,ww);
}
dfs_huan(1,1);
memset(vis,0,sizeof vis);
for (int i=1;i<=idx;++i) vis[h[i]]=1;
for (int i=1;i<=idx;++i)
dis[h[i]]=h_to_son(h[i],0);
for (int i=1;i<=idx;++i)
{
d[i]=d[i+idx]=dis[h[i]];
s[i+idx]=s[i]+s[idx];
}
build(1,idx<<1,root);
for (int i=1;i<=idx;++i)
{
maxn=llmin;
ans=min(ans,query(i,i+idx-1,root));
}
for (int i=1;i<=N;++i) dis[i]=llmax;
for (int i=1;i<=idx;++i)
ans=max(ans,find_son_dist(h[i]));
printf(
return 0;
}
Comments NOTHING