[SDOI2017]树点涂色(LCT)

题目

题目

参考

题解:
https://www.luogu.com.cn/blog/Soulist/solution-p3703
讨论:
https://www.luogu.com.cn/discuss/show/209134
https://www.luogu.com.cn/discuss/show/192352

做法

妙啊。

这道题目。

妙啊。

考虑用LCT。

我们在LCT,同色的联通块就在同一个Splay上(很明显每个同色联通块是一条链),而对于一个点到根节点的权,其实就是走到根节点的过程中,走过虚链的个数+1,所以不妨用(DFS)序+线段树维护每个点到根节点的虚链个数。

我们发现(1)操作其实就是LCT的(access)操作,但是对应的,树的结构也发生了改变,所以需要重新计算虚链个数。

通过观察普通(ace)的过程:

void access( int x ) {
	for( int y = 0; x; y = x, x = t[y].fa )
    	Splay(x), t[x].son[1] = y, pushup(x);
}

发现总共三步:

  1. 先将 (x) 旋到(Splay)根。
  2. (x) 的右儿子变虚
  3. (x) 的虚儿子(y) 变实。

于是,对应的,设(x)的右儿子的树层数最小的点为z,在原树上,(z)的层数为(x)的层数(+1),由于(x-z)这条边由实变虚,所以(z)的子树到根节点需要多走一条虚边,对应在线段树上整体(+1),而第三步由虚变实,则是(-1)

但是由于需要用到找根操作,在讨论中,许多人都在讨论找根不(splay)时间复杂度是假的,事实上,由于找根在(access)中,所以(splay)了也是假的,所以采用讨论中的做法,额外用(c)记录层数最小的点即可。

(2)操作,我们设(val(x))(x)到根节点所经过的虚链个数(+1),那么答案就是(val(x)+val(y)-2*val(lca(x,y))+1),至于为什么要(+1),因为这样子打会没有算上(lca)的颜色,所以要(+1),而且由于(val)函数中的(+1)会前后抵消,所以我代码中的(val)函数并没有(+1)

(3)操作则更加简单,直接在对应子树找最大即可。

树链剖分的话,实际上是模拟(access),他们每次找到(x)所在的颜色,和颜色对应的一段,在这一段上进行跳重链,实际上是对应了(access)中的一次(splay)操作,然后取消右儿子的操作,但是由于(access)操作总共会跳最多(mlog{n})次的(splay)(这里我的计算方法是(LCT)时间复杂度是(mlog{n})的,假设每次(splay)都只有一次(rotate),但实际上这种算法及其不靠谱,但至少不会超过这个上界),而每一个(splay)对应着一段颜色,用树剖跳一段颜色是(O(log^2n))的,那么应该是(O(mlog^3n))

但是我的分析方法太暴力了,又没有均摊,可能真的就是他们说的O(nlog^2n)吧,大概吧,希望有大佬知道告知一下。

代码

#include<cstdio>
#include<cstring>
#define  N  110000
#define  NN  210000
using  namespace  std;
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
inline  void  zwap(int  &x,int  &y){x^=y^=x^=y;}
int  val[N];
int  n,m;
namespace  A//线段树
{
	struct  node
	{
		int  l,r,c,lazy;
	}tr[NN];int  len;
	inline  void  updata(int  x){tr[x].c=mymax(tr[tr[x].l].c,tr[tr[x].r].c);}
	inline  void  pushlazy(int  x,int  d){tr[x].c+=d;tr[x].lazy+=d;}
	inline  void  downdata(int  x)
	{
		if(tr[x].lazy)
		{
			pushlazy(tr[x].l,tr[x].lazy);pushlazy(tr[x].r,tr[x].lazy);
			tr[x].lazy=0;
		}
	}
	inline  void  bt(int  l,int  r)
	{
		int  now=++len;
		if(l==r)tr[now].c=val[l];
		else
		{
			int  mid=(l+r)>>1;
			tr[now].l=len+1;bt(l,mid);
			tr[now].r=len+1;bt(mid+1,r);
			updata(now);
		}
	}
	void  change(int  now,int  l,int  r,int  ll,int  rr,int  k)
	{
		if(l==ll  &&  r==rr){pushlazy(now,k);return  ;}
		int  mid=(l+r)>>1;
		downdata(now);
		if(rr<=mid)change(tr[now].l,l,mid,ll,rr,k);
		else  if(mid<ll)change(tr[now].r,mid+1,r,ll,rr,k);
		else  change(tr[now].l,l,mid,ll,mid,k),change(tr[now].r,mid+1,r,mid+1,rr,k);
		updata(now);
	} 
	int  findans(int  now,int  l,int  r,int  ll,int  rr)
	{
		if(l==ll  &&  r==rr)return  tr[now].c;
		int  mid=(l+r)>>1;
		downdata(now);
		if(rr<=mid)return  findans(tr[now].l,l,mid,ll,rr);
		else  if(mid<ll)return  findans(tr[now].r,mid+1,r,ll,rr);
		else  return  mymax(findans(tr[now].l,l,mid,ll,mid),findans(tr[now].r,mid+1,r,mid+1,rr));
	}
}
namespace  B//Splay
{
	struct  node
	{
		int  son[2],f,c;
	}tr[N];
	inline  bool  nroot(int  x){return  !(tr[tr[x].f].son[0]==x  ||  tr[tr[x].f].son[1]==x);}
	inline  int  pd_son(int  x){return  tr[tr[x].f].son[0]==x?0:1;}
	inline  void  updata(int  x){!tr[x].son[0]?tr[x].c=x:tr[x].c=tr[tr[x].son[0]].c;}
	inline  void  rotate(int  x)
	{
		int  s=pd_son(x),f=tr[x].f,ff=tr[f].f;
		tr[x].f=ff;if(!nroot(f)/*他不是根*/)tr[ff].son[pd_son(f)]=x;
		tr[f].son[s]=tr[x].son[s^1];if(tr[x].son[s^1])tr[tr[x].son[s^1]].f=f;
		tr[x].son[s^1]=f;tr[f].f=x;
		updata(f);updata(x);updata(ff);
	}
	int  sta[N],top;
	void  splay(int  x)
	{
		while(!nroot(x))
		{
			int  f=tr[x].f;
			if(nroot(f)){rotate(x);break;}
			if(pd_son(f)==pd_son(x))rotate(f);
			else  rotate(x);
			rotate(x);
		}
	}
}
struct  node
{
	int  y,next;
}a[NN];int  len,last[N];
inline  void  ins(int  x,int  y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
int  dfn[N],dl[N],dr[N],ti;
int  fa[N][20],dep[N];
void  dfs(int  x)
{
	for(int  i=1;i<=16;i++)
	{
		fa[x][i]=fa[fa[x][i-1]][i-1];
		if(!fa[x][i])break;
	}
	dfn[x]=++ti;val[ti]=dep[x];dl[x]=ti;
	for(int  k=last[x];k;k=a[k].next)
	{
		int  y=a[k].y;
		if(!dfn[y])fa[y][0]=x,B::tr[y].f=x,dep[y]=dep[x]+1,dfs(y);
	}
	dr[x]=ti;
}
inline  int  lca(int  x,int  y)
{
	if(dep[x]>dep[y])x^=y^=x^=y;
	for(int  i=16;i>=0;i--)
	{
		if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
	}
	if(x==y)return  x;
	for(int  i=16;i>=0;i--)
	{
		if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
	}
	return  fa[x][0];
}
void  ace(int  x)
{
	for(int  y=0;x;x=B::tr[y=x].f)
	{
		B::splay(x);
		if(B::tr[x].son[1])
		{
			int  rt=B::tr[B::tr[x].son[1]].c;
			A::change(1,1,n,dl[rt],dr[rt],1);
		}
		if(B::tr[x].son[1]=y)
		{
			int  rt=B::tr[y].c;
			A::change(1,1,n,dl[rt],dr[rt],-1);
		}
	}
}
int  main()
{
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	dep[0]=-1;
	scanf("%d%d",&n,&m);
	for(int  i=1;i<n;i++)
	{
		int  x,y;scanf("%d%d",&x,&y);
		ins(x,y);ins(y,x);
	}
	dfs(1);//一个DFS处理了一万个东西 
	A::bt(1,n);
	for(int  i=1;i<=n;i++)B::tr[i].c=i;
	for(int  i=1;i<=m;i++)
	{
		int  type,x,y;
		scanf("%d",&type);
		if(type==1)
		{
			scanf("%d",&x);
			ace(x);
		}
		else  if(type==2)
		{
			scanf("%d%d",&x,&y);
			int  z=lca(x,y);
			printf("%d
",A::findans(1,1,n,dfn[x],dfn[x])+A::findans(1,1,n,dfn[y],dfn[y])-2*A::findans(1,1,n,dfn[z],dfn[z])+1);
		}
		else
		{
			scanf("%d",&x);
			printf("%d
",A::findans(1,1,n,dl[x],dr[x])+1);
		}
	}
	return  0;
}
【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/zhangjianjunab/p/13809533.html