[文章目录]
Description
现有一棵树。您需要写一个树上倍增算法，以实现如下操作：
A x 新建一个节点，将它作为x节点的儿子，编号为当前节点总数+1。
Q k p1 p2 p3.... 查询p1,p2,p3...这些节点的LCA。其中k表示查询节点的个数。最初树上只有一个节点，编号为1。多个节点的LCA定义为：这些节点的公共祖先中深度最大的。n≤3000000 k≤1000。询问<=1000
对于所有询问，我们统计出dfs序最小和最大的两个点，这两个点的lca即为答案。
对于所有询问，我们将询问的编号扔到询问对应的两个点上，之后按照节点编号从大到小缩点，将该点上的所有询问编号与其父亲的合并，合并过程中暴力扫两个编号集合，如果发现两个相同编号，那么该编号的lca就是父亲节点。
分析复杂度：
对于每次合并：
统计相同编号的复杂度是O(siz1*siz2)的，总复杂度相当于所有节点中任选两个的方案数，
合并的时候如果父亲为空，那么直接将集合送给父亲。反之，则进行合并，复杂度O(siz2)，和上面的加上，等价于没有。
总复杂度 空间复杂度
虽然麻烦，但毕竟是一种方法，还是写了。当时是rank3 7900ms 还挺快。
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
using namespace std;
#define R register
#define N 3001000
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 char gc() {char ch=nc(); while(ch!='A'&&ch!='Q') ch=nc(); return ch;}
inline int read()
{
int re=0; char ch=nc();
while(!isdigit(ch)) ch=nc();
while(isdigit(ch)) re=re*10+(ch^'0'),ch=nc();
return re;
}
int n=1,m,id[N],fa[N],q[1100][1100],z[2100][2100],tot,ans[1100];
int tim,in[N],out[N],head[N],to[N],nxt[N],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
void dfs(int x)
{
in[x]=++tim;
for(int i=head[x];i;i=nxt[i]) dfs(to[i]);
out[x]=++tim;
}
int main()
{
R int T=read(); int *x;
while(T--)
{
if(gc()=='A') fa[++n]=read();
else for(*q[++m]=read(),x=q[m]+*q[m];x!=q[m];--x) *x=read();
}
for(R int i=2;i<=n;++i) add(fa[i],i);
dfs(1); int l,r,v1,v2,*y;
for(R int i=1;i<=m;++i)
{
l=tim+1; r=0;
for(x=q[i]+*q[i];x!=q[i];--x)
{
if(in[*x]<l) l=in[v1=*x];
if(out[*x]>r) r=out[v2=*x];
}
if(v1==v2) ans[i]=v1;
else
{
if(!id[v1]) id[v1]=++tot;
z[id[v1]][++*z[id[v1]]]=i;
if(!id[v2]) id[v2]=++tot;
z[id[v2]][++*z[id[v2]]]=i;
}
}
for(R int i=n;i>1;--i)
{
if(!id[v1=fa[i]]) id[v1]=id[i];
else
{
l=id[i]; r=id[v1];
for(x=z[l]+*z[l];x!=z[l];--x)
for(y=z[r]+*z[r];y!=z[r];--y)
if(*x==*y) ans[*x]=v1;
y=z[r];
for(x=z[l]+*z[l];x!=z[l];--x)
y[++*y]=*x;
}
}
for(R int i=1;i<=m;++i) printf("%d\n",ans[i]);
return 0;
}