BZOJ 1023 SHOI 2008 cactus 선인장 그림 선인장 DP

제목: 선인장 한 그루를 정해서 이 선인장의 직경을 구하다
우선Tarjan 축소점 쌍, 개vector 또는 체인 테이블은 각 점이 어떤 점 쌍에 속하는지, 그리고 각 점 쌍에 어떤 점이 있는지 기록한다.
어떤 두 켤레는 고리가 아닐 수도 있으니, 우리는 한 변을 보충해서 고리로 볼 수 있어, 품위를 손상시키지 않는다
DP를 켤 때마다 루프의 루트 노드 이외의 점을 먼저 열거하고 해당 점이 있는 다른 점에 대해 DP를 한 번 더합니다.
그리고 f[x]를 x를 뿌리로 하는 자선인장의 모든 점과 x 사이의 최대 거리로
그리고 우리는 단조로운 대기열로 답안을 갱신하여 결정점과 갱신점의 거리가 링 길이의 절반을 넘지 않도록 보증할 것이다
마지막으로 링에 있는 모든 점으로 링의 뿌리 노드의 f값을 업데이트하면 됩니다
전체 선인장의 뿌리 노드가 여러 개의 점 중 하나일 수 있으니 주의하시오

#include 
#include 
#include 
#include 
#include 
#define M 50500
#define INF 0x3f3f3f3f
using namespace std;
int n,m,k,cnt,ans=-INF;
namespace Cactus_Graph{
	int size[M],f[M];
	//f[x]   x             x     
	vector belong[M];
	vector contain[M];
	int Cactus_DP(int scc)
	{
		vector::iterator it;
		vector::reverse_iterator _it;
		for(_it=contain[scc].rbegin(),_it++;_it!=contain[scc].rend();_it++)
		{
			int x=*_it;
			for(it=belong[x].begin();it!=belong[x].end();it++)
				if( *it!=scc )
					f[x]=max(f[x],Cactus_DP(*it));
		}
		static pair q[M<<1];
		int re=-INF,r=0,h=0,limit=size[scc]>>1,pos=0;
		for(_it=contain[scc].rbegin();_it!=contain[scc].rend();_it++)
		{
			int x=*_it;++pos;

			while( r-h>=1 && f[q[r].first]+(pos-q[r].second)=1 && pos-q[h+1].second>=limit )
				++h;
		}
		for(_it=contain[scc].rbegin();_it!=contain[scc].rend();_it++)
		{
			int x=*_it;++pos;


			if(r-h>=1)
			ans=max(ans,f[q[h+1].first]+(pos-q[h+1].second)+f[x] );

			while( r-h>=1 && f[q[r].first]+(pos-q[r].second)=1 && pos-q[h+1].second>=limit )
				++h;
		}
		for(_it=contain[scc].rbegin(),pos=0;_it!=contain[scc].rend();_it++,pos++)
			re=max(re,f[*_it]+min(pos,size[scc]-pos) );
		return re;
	}
}
namespace Origin_Graph{
	struct abcd{
		int to,next;
	}table[M<<2];
	int head[M],tot=1;
	void Add(int x,int y)
	{
		table[++tot].to=y;
		table[tot].next=head[x];
		head[x]=tot;
	}
	void Tarjan(int x)
	{
		using namespace Cactus_Graph;

		static int dpt[M],low[M],T,stack[M],top;
		int i;
		
		dpt[x]=low[x]=++T;
		stack[++top]=x;

		for(i=head[x];i;i=table[i].next)
		{
			if(dpt[table[i].to])
				low[x]=min(low[x],dpt[table[i].to]);
			else
			{
				Tarjan(table[i].to),low[x]=min(low[x],low[table[i].to]);
				if(dpt[x]==low[table[i].to])
				{
					int t;++cnt;
					do{
						t=stack[top--];
						belong[t].push_back(cnt);
						contain[cnt].push_back(t);
						size[cnt]++;
					}while(t!=table[i].to);
					belong[x].push_back(cnt);
					contain[cnt].push_back(x);
					size[cnt]++;
				}
			}
		}
	}
}
int main()
{
	using namespace Origin_Graph;
	using namespace Cactus_Graph;
	int i,j,x,y;
	cin>>n>>m;
	for(i=1;i<=m;i++)
	{
		scanf("%d%d",&k,&x);
		for(j=2;j<=k;j++)
		{
			scanf("%d",&y);
			Add(x,y);Add(y,x);
			x=y;
		}
	}
	Tarjan(1);
	vector::iterator it;
	for(it=belong[1].begin();it!=belong[1].end();it++)
		f[1]=max(f[1],Cactus_DP(*it));
	cout<