LOJ6115 汇合树上分块

本题空间很小，那些O(nlogn)的树上lca算法在这里不顶用了，可以考虑树分块。

本题的树分块是基于深度的，即按深度每\(\sqrt n\)分一块，然后一块一块往上跳，一直跳到lca处。

对于这题，有这样几种做法：

考虑在树上选择若干关键点，每次求lca先往上跳到最近的关键点处，然后再一个一个关键点往上跳，直到跳到同一关键点处。至于关键点的选择，可以这样做：

从浅到深依次从每一个点出发，如果向上跳 2S-1 个节点都没有关键点,则将其 S 级祖先设为关键点。这样关键点个数严格小于 n/S , 同时每个关键点到它父亲方向的第一个关键点的距离都等于 S 。并且从每个点向上跳，到第一个关键点所需步数 < 2S 。

当然也可以在树上随机\(\sqrt n\)个关键点，这样复杂度期望是\(O(\sqrt n)\)的。

还有神仙psj提供的一种做法，就是记录下每个点向上跳\(\sqrt n\)次的祖先，然后每次查询的时候先将两个点跳到同一深度（深度可以在跳之前\(O(\sqrt n)\)查询得到，跳的时候动态维护），然后像倍增lca那样能往上跳就往上跳，只不过步长是\(\sqrt n\)的，最后在一步一步跳到lca处。这种做法的空间是上面做法的两倍，得卡一卡空间才能过。

这里我写的是第一种做法，具体细节可以参考代码：

#include<cstdio>

#include<bitset>

#include<algorithm>

using namespace std;

#define N 900007

#define M 5007

const int t=300;

int fa[N],a[M],top[M],dep[M],cnt;

bitset<N> tag;

void mark(int x)

{

	int v=fa[x],i;

	for(i=1;i<2*t&&!tag[v];i++)

		v=fa[v];

	if(i==2*t)

	{

		for(i=1;i<=t;i++)

			x=fa[x];

		a[++cnt]=x;

		tag[x]=1;

	}

}

int getpos(int x)

{

	int p=lower_bound(a+1,a+cnt+1,x)-a;

	return p;

}

int find(int x)

{

	while(!tag[x])x=fa[x];

	return x;

}

int getdep(int x,int y)

{

	int d=0;

	while(x!=y)

		d++,x=fa[x];

	return d;

}

int getkth(int x,int k)

{

	int i;

	for(i=1;i<=k;i++)

		x=fa[x];

	return x;

}

int main()

{

	int n,m,i,x,y;

	scanf("%d%d",&n,&m);

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

	{

		scanf("%d",&x);

		fa[i]=x;

	}

	tag[1]=1;

	a[++cnt]=1;

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

		mark(i);

	sort(a+1,a+cnt+1);

	dep[1]=1;

	for(i=2;i<=cnt;i++)

	{

		top[i]=getpos(find(fa[a[i]]));

		dep[i]=dep[top[i]]+1;

	}

	for(i=1;i<=m;i++)

	{

		scanf("%d%d",&x,&y);

		int u=find(x),v=find(y);

		u=getpos(u),v=getpos(v);

		if(dep[v]>dep[u])swap(x,y),swap(u,v);

		while(dep[u]>dep[v])

		{

			x=a[u];

			u=top[u];

		}

		while(u!=v)

		{

			x=a[u],u=top[u];

			y=a[v],v=top[v];

		}

		int dx=getdep(x,a[u]),dy=getdep(y,a[v]);

		if(dy>dx)swap(x,y),swap(dx,dy);

		x=getkth(x,dx-dy);

		while(x!=y)

			x=fa[x],y=fa[y];

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

	}

	return 0;

}

巴特西

LOJ6115 汇合树上分块

最新文章

热门文章

巴特西

LOJ6115 汇合 树上分块

最新文章

热门文章

LOJ6115 汇合树上分块