4679: Hdu5331 Simple Problem

题意：

考场上，看到这道题就让我想起BZOJ4712洪水。然后思路就被带着飞起了，完全没去考虑一条链的情况，于是GG.

解法：先考虑一条链的做法，可以用线段树维护一下，需要保留的信息：$F[0/1][0/1]$表示左端点不选/选，右端点不选/选的最多人数。在树上的做法，可以在重链上用线段树维护，对于轻边，就暴力更新其父亲（每个点存下了其轻边的答案），然后接着往上更新重链。

于是先离线，$O(n\log n)$。

在线做法，将上述做法扩展到LCT上。复杂度还是$O(n\log n)$

代码很丑 ⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

#include< cstdio >

#define gec getchar

#define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)

#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__);

typedef long long ll;

template

inline void read(T&x)

{

	x=0;bool f=0;char c=gec();

	for(;c<'0'||c>'9';c=gec())f=(c=='-');

	for(;c>='0'&&c<='9';c=gec())x=x*10+c-'0';

	x=f?-x:x;

}

const int MAXN(300010),INF(0x73f3f3f);

int n,ty,f,Father[MAXN],root;//编号全部+1

int max(int a,int b){return a>b?a:b;}

struct Data{int f[2][2];}zero;

struct LCT

{

	int fa[MAXN],nx[MAXN][2],F[MAXN],G[MAXN];//轻儿子的答案

	Data val[MAXN];//[1/0][1/0] 顶端选/不选 尾端选/不选

	int which(int x){if(nx[fa[x]][0]==x)return 0;if(nx[fa[x]][1]==x)return 1;return -1;}

	void update(int x)

	{

		if(nx[x][0]&&nx[x][1])

		for(int i=0;i<=1;i++) for(int j=0;j<=1;j++)

		{

			val[x].f[i][j]=max(max(val[nx[x][0]].f[i][1],val[nx[x][0]].f[i][0])+

			max(val[nx[x][1]].f[1][j],val[nx[x][1]].f[0][j])+F[x],

			val[nx[x][0]].f[i][0]+val[nx[x][1]].f[0][j]+G[x]);

		}

		else

		if(nx[x][0])

		for(int i=0;i<=1;i++)

		{

			val[x].f[i][0]=max(val[nx[x][0]].f[i][0],val[nx[x][0]].f[i][1])+F[x];

			val[x].f[i][1]=val[nx[x][0]].f[i][0]+G[x];

		}

		else

		if(nx[x][1])

		for(int i=0;i<=1;i++)

		{

			val[x].f[0][i]=max(val[nx[x][1]].f[0][i],val[nx[x][1]].f[1][i])+F[x];

			val[x].f[1][i]=val[nx[x][1]].f[0][i]+G[x];

		}else

		{

			val[x].f[1][1]=G[x]; val[x].f[0][0]=F[x];

			val[x].f[0][1]=val[x].f[1][0]=0;

		}

	}

	void rotate(int x)

	{

		int ff=fa[x],fafa=fa[ff],fd=which(ff),xd=which(x);

		fa[nx[x][xd^1]]=ff;

		nx[ff][xd]=nx[x][xd^1];

		nx[x][xd^1]=ff;fa[ff]=x;

		fa[x]=fafa;if(fd!=-1)nx[fafa][fd]=x;

		update(ff);

	}

	void splay(int x)

	{

		if(!x)return;

		while(which(x)!=-1)

		{

			if(which(fa[x])==-1)rotate(x);

			else

			{

				if(which(fa[x])^which(x))rotate(fa[x]),rotate(x);

				else rotate(x),rotate(x);

			}

		}

		update(x);

	}

	void Look()

	{

		for(int i=1;i<=n+1;i++)

		{

			fprintf(stderr,"i:%d Fa:%d n0:%d n1:%d F:%d G:%d\n",i,fa[i],nx[i][0],nx[i][1],F[i],G[i]);

			fprintf(stderr,"v00:%d v01:%d v10:%d v11:%d\n",val[i].f[0][0],val[i].f[0][1],val[i].f[1][0],val[i].f[1][1]);

		}

	}

	void access(int x,int t)

	{

		int Fr,Gr,Fl=0,Gl=0,Tf,Tg;

		while(x)

		{

			splay(x);update(nx[x][1]);

//			fprintf(stderr,"x:%d\n",x);

			Fr=max(val[nx[x][1]].f[0][0],val[nx[x][1]].f[0][1]);

			Gr=max(val[nx[x][1]].f[1][0],val[nx[x][1]].f[1][1]);

//			fprintf(stderr,"Fr:%d Gr:%d\n",Fr,Gr);

//			fprintf(stderr,"Fl:%d Gl:%d\n",Fl,Gl);

			Tf=max(val[x].f[0][0],val[x].f[0][1]);

			Tg=max(val[x].f[1][0],val[x].f[1][1]);

//			fprintf(stderr,"Tf:%d Tg:%d\n",Tf,Tg);

			F[x]+=max(Fr,Gr);G[x]+=Fr;

			F[x]-=max(Fl,Gl),G[x]-=Fl;

			Fl=Tf; Gl=Tg;

			nx[x][1]=t;update(x);

			t=x;x=fa[x];

		}

		splay(1);

//		Look();

	}

	void link(int a,int b)//a is b's father

	{

		fa[b]=a; access(a,b);

	}

	void New(int x)

	{F[x]=0;G[x]=1;update(x);}

	int ask(int x)

	{

		splay(x);

		return max(val[x].f[0][0],max(val[x].f[1][1],max(val[x].f[1][0],val[x].f[0][1])));

	}

}tree;

int Ans;

void Back()

{

	for(int i=1;i<=n+1;i++)

	{

		tree.fa[i]=tree.nx[i][0]=tree.nx[i][1]=tree.F[i]=tree.G[i]=0;

		tree.val[i]=zero;

	}

}

int main()

{

#ifndef ONLINE_JUDGE

	FILE("party");

#endif

	while(scanf("%d",&n)!=EOF)

	{

		n--;Back();

		root=1;tree.New(1);

		for(int i=2;i<=n+1;i++)

		{

			read(f);

			tree.New(i);

			tree.link(++f,i);

	//		fprintf(stderr,"a:%d b:%d\n",f,i);

			Ans=tree.ask(1);

			printf("%d\n",Ans);

		}

	}

	return 0;

}

巴特西

BZOJ 4679/Hdu5331 Simple Problem LCT or 树链剖分

4679: Hdu5331 Simple Problem

最新文章

热门文章