换根树剖学习笔记

有些树上操作题目需要换根操作，用普通的树链剖分无法解决此类问题。这时我们就需要改造一下树剖，令它支持换根操作。

首先肯定不可能每次都重新剖分，因为那样会 TLE。那么考虑以 $1$ 为根剖，记下当前的跟 $rt$ ，对于每个操作特殊处理。

最近公共祖先

考虑用 $\operatorname{lca}(x,y)$ 表示以 $1$ 为根时 $x$ 和 $y$ 的最近公共祖先，用 $\operatorname{LCA}(x,y)$ 表示换根后 $x$ 和 $y$ 的最近公共祖先（这里默认 $x$ 深度小于等于 $y$ ）。

若 $\operatorname{lca}(x,y)=x$ ：（图中绿色节点是 $x$ ，红色节点是 $y$ ，不同颜色的节点是不同情况下 $rt$ 的位置）

(1) 若 $rt$ 位于黄色区域，即 $\operatorname{lca}(x,rt)=x\land\operatorname{lca}(y,rt)=y$ ，那么 $\operatorname{LCA}(x,y)=y$

(2) 若 $rt$ 位于橙色区域，即 $\operatorname{lca}(x,rt)=x\land\operatorname{lca}(y,rt)\not=y$ ，那么 $\operatorname{LCA}(x,y)=\operatorname{lca}(y,rt)$

(3) 若 $rt$ 位于粉色区域，即 $\operatorname{lca}(x,rt)\not=x$ ，那么 $\operatorname{LCA}(x,y)=\operatorname{lca}(x,y)$

若 $\operatorname{lca}(x,y)\not=x$ ：（图中绿色节点是 $x$ ，红色节点是 $y$ ，不同颜色的节点是不同情况下 $rt$ 的位置）

(1) 若 $rt$ 位于灰色区域，即 $\operatorname{lca}(x,rt)=x$ ，那么 $\operatorname{LCA}(x,y)=x$

(2) 若 $rt$ 位于蓝色区域，即 $\operatorname{lca}(x,rt)=y$ ，那么 $\operatorname{LCA}(x,y)=y$

(3) 若 $rt$ 位于粉色区域，即 $\operatorname{lca}(x,rt)=\operatorname{lca}(y,rt)$ ，那么 $\operatorname{LCA}(x,y)=\operatorname{lca}(x,y)$

(4) 若 $rt$ 位于橙色区域，即 $(\operatorname{lca}(x,rt)=rt\land\operatorname{lca}(y,rt)=\operatorname{lca}(x,y))\lor(\operatorname{lca}(x,rt)=\operatorname{lca}(x,y)\land\operatorname{lca}(y,rt)=y)$ ，那么 $\operatorname{LCA}(x,y)=rt$

(5) 若以上条件均不满足，那么若 $\operatorname{lca}(x,rt)=\operatorname{lca}(x,y)$ ，那么 $\operatorname{LCA}(x,y)=\operatorname{lca}(x,rt)$ ，否则 $\operatorname{LCA}(x,y)=\operatorname{lca}(y,rt)$

代码如下：

inline int getLCA(int x,int y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	int xr=getlca(x,rt),yr=getlca(y,rt),xy=getlca(x,y);
	if(xy==x)
	{
		if(xr==x&&yr==y)
		{
			return y;
		}
		if(xr==x)
		{
			return yr;
		}
		return x;
	}
	else
	{
		if(xr==x||yr==y)
		{
			return xr==x?x:y;
		}
		if(xr==yr)
		{
			return xy;
		}
		if((xr==rt&&yr==xy)||(xr==xy&&yr==rt))
		{
			return rt;
		}
		return xr==xy?yr:xr;
	}
}

链上询问/修改

显然无论根怎么换，链 $(u,v)$ 上的节点都不会改变，所以直接修改即可。

子树内询问/修改

图中绿色节点是 $x$ 。

若 $rt=x$ ，那么查询/修改整棵子树
若 $rt$ 位于黄色区域，即 $\operatorname{lca}(x,rt)=x，那么查询/修改 $x$ 子树除了 $rt$ 方向儿子的子树外所有的节点
否则说明 $rt$ 位于粉色区域，那么查询/求改 $x$ 子树即可

代码如下：

inline int jump(int x,int k)
{
	for(int i=25;i>=0;i--)
	{
		if(k&(1<<i))
		{
			x=up[x][i];
		}
	}
	return x;
}

inline int quesubtree(int x)
{
	if(x==rt)
	{
		return que(1,1,n,1,n);
	}
	int xr;
	if(dep[rt]>dep[x]&&up[xr=jump(rt,dep[rt]-dep[x]-1)][0]==x)
	{
		if(id[xr]==1)
		{
			return que(1,1,n,R[xr]+1,n);
		}
		if(R[xr]==n)
		{
			return que(1,1,n,1,id[xr]-1);
		}
		return min(que(1,1,n,1,id[xr]-1),que(1,1,n,R[xr]+1,n));
	}
	return que(1,1,n,id[x],R[x]);
}

模板题代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const long long S=1000005,MS=100005;
const int inf=2147483647;

int n,m,val[MS];
int esum,to[S],nxt[S],h[MS];
int up[MS][30],dep[MS],siz[MS],hson[MS];
int cnt,id[MS],top[MS],a[MS],R[MS];
int minn[MS<<2],lazy[MS<<2];
int rt;

inline void add(int x,int y)
{
	to[++esum]=y;
	nxt[esum]=h[x];
	h[x]=esum;
}

void dfs1(int u,int fa) 
{
	up[u][0]=fa;
	for(int i=1;i<=25;i++)
	{
		up[u][i]=up[up[u][i-1]][i-1];
	}
	dep[u]=dep[fa]+1;
	siz[u]=1;
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==fa)
		{
			continue;
		}
		dfs1(v,u);
		siz[u]+=siz[v];
		if(siz[v]>siz[hson[u]])
		{
			hson[u]=v;
		}
	}
}

void dfs2(int u,int tpf)
{
	id[u]=++cnt;
	top[u]=tpf;
	a[cnt]=val[u];
	if(hson[u]!=0)
	{
		dfs2(hson[u],tpf);
	}
	for(int i=h[u];i;i=nxt[i])
	{
		int v=to[i];
		if(v==up[u][0]||v==hson[u])
		{
			continue;
		}
		dfs2(v,v);
	}
	R[u]=cnt;
}

void build(int u,int l,int r)
{
	lazy[u]=-1;
	if(l==r)
	{
		minn[u]=a[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	minn[u]=min(minn[u<<1],minn[u<<1|1]);
}

void upd(int u,int l,int r,int L,int R,int k)
{
	if(l>R||r<L)
	{
		return;
	}
	if(l>=L&&r<=R)
	{
		minn[u]=k;
		lazy[u]=k;
		return;
	}
	if(lazy[u]!=-1)
	{
		minn[u<<1]=lazy[u];
		minn[u<<1|1]=lazy[u];
		lazy[u<<1]=lazy[u];
		lazy[u<<1|1]=lazy[u];
		lazy[u]=-1;
	}
	int mid=l+r>>1;
	if(L<=mid)
	{
		upd(u<<1,l,mid,L,R,k);
	}
	if(R>=mid+1)
	{
		upd(u<<1|1,mid+1,r,L,R,k);
	}
	minn[u]=min(minn[u<<1],minn[u<<1|1]);
}

int que(int u,int l,int r,int L,int R)
{
	if(l>R||r<l)
	{
		return inf;
	}
	if(l>=L&&r<=R)
	{
		return minn[u];
	}
	if(lazy[u]!=-1)
	{
		minn[u<<1]=lazy[u];
		minn[u<<1|1]=lazy[u];
		lazy[u<<1]=lazy[u];
		lazy[u<<1|1]=lazy[u];
		lazy[u]=-1;
	}
	int mid=l+r>>1,res=inf;
	if(L<=mid)
	{
		res=min(res,que(u<<1,l,mid,L,R));
	}
	if(R>=mid+1)
	{
		res=min(res,que(u<<1|1,mid+1,r,L,R));
	}
	return res;
}

inline int jump(int x,int k)
{
	for(int i=25;i>=0;i--)
	{
		if(k&(1<<i))
		{
			x=up[x][i];
		}
	}
	return x;
}

inline int getlca(int x,int y)
{
	if(dep[x]<dep[y])
	{
		swap(x,y);
	}
	for(int i=25;i>=0;i--)
	{
		if(dep[up[x][i]]>=dep[y])
		{
			x=up[x][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=25;i>=0;i--)
	{
		if(up[x][i]!=up[y][i])
		{
			x=up[x][i];
			y=up[y][i];
		}
	}
	return up[x][0];
}

inline int getLCA(int x,int y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	int xr=getlca(x,rt),yr=getlca(y,rt),xy=getlca(x,y);
	if(xy==x)
	{
		if(xr==x&&yr==y)
		{
			return y;
		}
		if(xr==x)
		{
			return yr;
		}
		return x;
	}
	else
	{
		if(xr==x||yr==y)
		{
			return xr==x?x:y;
		}
		if(xr==yr)
		{
			return xy;
		}
		if((xr==rt&&yr==xy)||(xr==xy&&yr==rt))
		{
			return rt;
		}
		return xr==xy?yr:xr;
	}
}

inline void updpath(int x,int y,int k)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]>dep[top[y]])
		{
			upd(1,1,n,id[top[x]],id[x],k);
			x=up[top[x]][0];
		}
		else
		{
			upd(1,1,n,id[top[y]],id[y],k);
			y=up[top[y]][0];
		}
	}
	upd(1,1,n,min(id[x],id[y]),max(id[x],id[y]),k);
}

inline int quesubtree(int x)
{
	if(x==rt)
	{
		return que(1,1,n,1,n);
	}
	int xr;
	if(dep[rt]>dep[x]&&up[xr=jump(rt,dep[rt]-dep[x]-1)][0]==x)
	{
		if(id[xr]==1)
		{
			return que(1,1,n,R[xr]+1,n);
		}
		if(R[xr]==n)
		{
			return que(1,1,n,1,id[xr]-1);
		}
		return min(que(1,1,n,1,id[xr]-1),que(1,1,n,R[xr]+1,n));
	}
	return que(1,1,n,id[x],R[x]);
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&val[i]);
	}
	scanf("%d",&rt);
	dfs1(1,0);
	dfs2(1,1);
	build(1,1,n);
	while(m--)
	{
		int op;
		scanf("%d",&op);
		if(op==1)
		{
			scanf("%d",&rt);
		}
		else if(op==2)
		{
			int x,y,k;
			scanf("%d%d%d",&x,&y,&k);
			updpath(x,y,k);
		}
		else
		{
			int x;
			scanf("%d",&x);
			printf("%d\n",quesubtree(x));
		}
	}
	return 0;
}

练习题目

CF916E Jamie and Tree

换根树剖学习笔记

练习题目

感谢您的支持，我会继续努力的!