lp4244 SHOI2008 仙人掌图 II

仙人掌图是每一个点双都只有一个环的连通图。
对于一个仙人掌图，它在许多方面都有树的性质，只是其中的有一些节点被换成了环。
我们不妨依然采用一种伪树形DP的方式来处理这棵树，我们发现，非环节点的转移都是非常容易达成了，问题在于环上的节点的转移。

首先，我们要找到这个环，这可以用Tarjan算法来完成。
具体来说，我们维护两个数组：dfn和lw，其中前者表示的是某一个节点的dfs序，后者表示的是某一个节点至多走一条返祖边或者父亲边能够到达的最小dfs序。
显然，在搜索中，如果下一个节点未被访问过，我们就可以在搜索完它以后将当前节点的lw与它的lw取较小值。
否则，当前节点通向它的边一定是一条返祖边或者父亲边，那么当前节点的lw值应当与它的dfs序取较小值。

对于一个环，我们如果将它视为一个节点，我们想一想要怎么从它的「孩子」们处转移呢？
我们发现，依次枚举它的每一个孩子，答案显然是：
$$max(f_i+f_j+dis_{i,j})$$
这个式子可以使用单调队列优化。所以我们每一次把一个环提出来瞎DP一下就好了。

#include<iostream>
#include<cstdio>
#include<deque>
#define Fv(A,U) for(int A=h[U];A;A=e[A].nxt)

inline int Min(int A,int B){
	return A<B?A:B;
}
inline int Max(int A,int B){
	return A>B?A:B;
}

struct ee{
	int v;
	int nxt;
}e[200005];
int et=0,h[100005];
inline void Eadd(int U,int V){
	e[++et]=(ee){V,h[U]};
	h[U]=et;
}
inline void add(int U,int V){
	Eadd(U,V);
	Eadd(V,U);
}

int n,m;
int dfn[100005],lw[100005],dep[100005],fa[100005],cnt=0;
int ans=0,f[100005],a[100005];
std::deque<int> q;
inline void calc(int X,int Y){
	int tot=dep[Y]-dep[X]+1;
	int nw=tot;
	for(int i=Y;i!=X;i=fa[i]){
		a[nw--]=f[i];
	}
	a[nw]=f[X];
	for(int i=1;i<=tot;++i){
		a[tot+i]=a[i];
	}
	while(!q.empty()){
		q.pop_front();
	}
	q.push_back(1);
	for(int i=2;i<=(tot<<1);++i){
		while(!q.empty()&&i-q.front()>(tot>>1)){
			q.pop_front();
		}
		if(!q.empty()){
			ans=Max(ans,a[i]+a[q.front()]+i-q.front());
		}
		while(!q.empty()&&a[q.back()]-q.back()<a[i]-i){
			q.pop_back();
		}
		q.push_back(i);
	}
	for(int i=2;i<=tot;++i){
		f[X]=Max(f[X],a[i]+Min(i-1,tot-i+1));
	}
}
inline void dfs(int X,int FA){
	dfn[X]=lw[X]=++cnt;
	Fv(i,X){
		if(e[i].v!=FA){//这一句如果不加会无形降低很多点的lw值，从而使环的大小变成0。 
			if(!dfn[e[i].v]){
				fa[e[i].v]=X;
				dep[e[i].v]=dep[X]+1;
				dfs(e[i].v,X);
				lw[X]=Min(lw[X],lw[e[i].v]);
			}else{
				lw[X]=Min(lw[X],dfn[e[i].v]);
			}
			if(lw[e[i].v]>dfn[X]){
				ans=Max(ans,f[X]+f[e[i].v]+1);
				f[X]=Max(f[X],f[e[i].v]+1);
			}
		}
		
	}
	Fv(i,X){
		if(fa[e[i].v]!=X&&dfn[X]<dfn[e[i].v]){
			calc(X,e[i].v);
		}
	}
}

void init(){
	scanf("%d%d",&n,&m);
	int u,v,x;
	for(int i=1;i<=m;++i){
		u=0;
		scanf("%d",&x);
		for(int j=1;j<=x;++j){
			scanf("%d",&v);
			if(u){
				add(u,v);
			}
			u=v;
		}
	}
	dfs(1,0);
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}