BZOJ 5165 树上倍增

题目大意

给你一棵$3 \times 10^6$个节点的树，$1000$次询问每次询问$k(k \le 1000)$个点的LCA.

LCA好题。

这题卡空间而且题目是“倍增”所以自然不得使用$n \log n$的算法。树的节点个数很多，查询次数却很少，所以需要用其他算法进行更新。

一种做法是用树剖LCA解决问题，DFS两次进行预处理，每次查询log n,时间复杂度$O(m \log n + n)$.

还有一种更高级的做法：首先做一个DFS序，之后在其上建立线段树，维护深度信息。每次查询的时候查询DFS序最小和DFS序最大的点的LCA即可。

我写的是第一种。

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
#define N 3000010
int fa[N],son[N],siz[N],top[N],q[1000010],l[1010],r[1010],totq,totp=1,depth[N];
int to[N],nxt[N],head[N],tot;
inline char nc()
{
	static char buf[100000],*p1,*p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int RI()
{
	int ret=0;char tmp=nc();
	while(!isdigit(tmp)) tmp=nc();
	while(isdigit(tmp)) ret=ret*10+(tmp^'0'),tmp=nc();
	return ret;
}
inline bool ADD()
{
	char tmp=nc();
	while(tmp!='A'&&tmp!='Q') tmp=nc();
	return tmp=='A';
}
inline void AE(int x,int y){to[++tot]=y,nxt[tot]=head[x],head[x]=tot;}
void DFS1(int pos)
{
	siz[pos]=1;
	for(int i=head[pos];i;i=nxt[i])
	{
		depth[to[i]]=depth[pos]+1,fa[to[i]]=pos,DFS1(to[i]),siz[pos]+=siz[to[i]];
		if(siz[to[i]]>siz[son[pos]]) son[pos]=to[i];
	}
}
void DFS2(int pos,int pre)
{
	top[pos]=pre;
	if(son[pos]) DFS2(son[pos],pre);
	for(int i=head[pos];i;i=nxt[i])
		if(to[i]!=son[pos])
			DFS2(to[i],to[i]);
}
inline int LCA(int x,int y)
{
	while(top[x]!=top[y])
		depth[top[x]]>depth[top[y]]?x=fa[top[x]]:y=fa[top[y]];
	return depth[x]<depth[y]?x:y;
}
int main()
{
	int T=RI(),tmp;
	while(T--)
	{
		if(ADD()) AE(RI(),++totp);
		else
		{
			++totq,l[totq]=r[totq-1]+1,r[totq]=l[totq]+RI()-1;
			for(int i=l[totq];i<=r[totq];++i) q[i]=RI();
		}
	}
	depth[1]=1,DFS1(1),DFS2(1,1);
	int ans,i,j;
	for(i=1;i<=totq;++i)
	{
		ans=q[l[i]];
		for(j=l[i]+1;j<=r[i]&&ans!=1;++j) ans=LCA(ans,q[j]);
		printf("%d\n",ans);
	}
	return 0;
}