【bzoj1023】[SHOI2008]cactus仙人掌圖

http://z55250825.blog.163.com/blog/static/150230809201412793151890/

%%%%

反正自己就是sb。。第一道仙人掌dp。。。 感覺很神奇啊

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;


char c;
inline void read(int &a)
{a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();}
int F[300001];
int line[709001],l,r;
int low[300001],now[300001],f[300001],deep[300001];
int fa[100001];
int cnt;
struct Chain
{Chain*next;int other;Chain(){next=NULL;}}*Head[300001];
inline void addside(int x,int y)
{Chain *tp=new Chain;tp->next=Head[x];tp->other=y;Head[x]=tp;}
inline int abs(int a){return a<0?-a:a;}
inline int min(int a,int b){return a<b?a:b;}
inline int max(int a,int b){return a>b?a:b;}
int a[300001];
int ans;
inline void dp(int root,int u)
{
	int n,i;
	if(deep[root]>deep[u])swap(root,u);
	n=abs(deep[root]-deep[u])+1;
	l=1,r=1;
	for(i=u;i!=root;i=fa[i])
	    a[n--]=f[i];
	a[n]=f[root];
	n=abs(deep[root]-deep[u])+1;
	for(i=1;i<=n;i++)a[i+n]=a[i];
	line[1]=1;
	for(i=2;i<=n<<1;i++)
	   {
	   	 while(l<=r&&i-line[l]>(n>>1))l++;
	   	 ans=max(ans,a[line[l]]+a[i]+i-line[l]);
	   	 while(l<=r&&a[line[r]]-line[r]<=a[i]-i)r--;
	   	 line[++r]=i;
	   }
	for(i=2;i<=n;i++)
	  f[root]=max(f[root],min(i-1,n-i+1)+a[i]);
}
void dfs(int u)
{
   now[u]=low[u]=++cnt;
   for(Chain *tp=Head[u];tp;tp=tp->next)
      if(tp->other!=fa[u])
        {
        	if(now[tp->other]==0)
        	    deep[tp->other]=deep[u]+1,fa[tp->other]=u,dfs(tp->other);
        	low[u]=min(low[u],low[tp->other]);
        	if(low[tp->other]>now[u])
        	    ans=max(ans,1+f[u]+f[tp->other]),
				f[u]=max(f[u],f[tp->other]+1);
        }
    for(Chain *tp=Head[u];tp;tp=tp->next)
      if(u!=fa[tp->other]&&now[u]<now[tp->other])
          dp(u,tp->other); 
}

int main()
{
	int i,j,k,t,n,m,p;
	read(n),read(m);
	for(i=1;i<=m;i++)
	  {
	  	read(k);
	  	read(j);
	  	for(t=2;t<=k;t++)
	     read(p),addside(j,p),addside(p,j),j=p;
	  }
	fa[1]=1;
	dfs(1);
	printf("%d\n",ans);
	return 0;
}