[bzoj3242]-[NOI2013]快餐店

发布于 2017-12-11  119 次阅读



题目(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;
}