本文主要是用于警示自己避免犯错。
参考代码
dfs 序求 lca 的参考代码如下。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+10,MAXLOG2N=20;
int N,M,S,cnt,head[MAXN],dfn[MAXN],dfncnt,stlca[MAXLOG2N][MAXN],LOG2[MAXN],deep[MAXN],anc[MAXN];
struct EDGE
{
int v,nxt;
}edge[MAXN<<1];
void add(int u,int v)
{
++cnt;
edge[cnt].v=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
}
void dfs(int u)
{
stlca[0][dfn[u]=++dfncnt]=u;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(v!=anc[u]){anc[v]=u;deep[v]=deep[u]+1;dfs(v);}
}
}
int deepget(int u,int v)//得到深度浅的节点
{
return deep[u]<deep[v]?u:v;
}
void stlca_init()
{
//求解log2部分
for(int i=2;i<=N;++i){LOG2[i]=LOG2[i>>1]+1;}
//建ST表部分
for(int j=1;(1<<j)<=N;++j)
{
int temp=N-(1<<j)+1;
for(int i=1;i<=temp;++i)
{
stlca[j][i]=deepget(stlca[j-1][i],stlca[j-1][i+(1<<(j-1))]);
}
}
}
int lca(int u,int v)
{
if(u==v)return u;
if(dfn[u]>dfn[v])swap(u,v);//保持dfn[u]<dfn[v]
int k=LOG2[dfn[v]-dfn[u]];
int lcason=deepget(stlca[k][dfn[u]+1],stlca[k][dfn[v]-(1<<k)+1]);
return anc[lcason];
}
int main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin>>N>>M>>S;
for(int i=1;i<N;++i)
{
int x,y;cin>>x>>y;
add(x,y);
add(y,x);
}
deep[S]=1;//根节点深度为1好看
dfs(S);
stlca_init();
while(M--)
{
int a,b;cin>>a>>b;
cout<<lca(a,b)<<'\n';
}
return 0;
}
常见错误
- 无向边存储时少一次变成有向边。
太（）（）了。
- dfs 过程中忘记添加祖先及深度的记录。
void dfs(int u)
{
stlca[0][dfn[u]=++dfncnt]=u;
for(int i=head[u];i;i=edge[i].nxt)
{
int v=edge[i].v;
if(v!=anc[u])dfs(v);
}
}
这都能写错？？？
- 查找深度小的节点的函数写错。
int deepget(int u,int v)//得到深度浅的节点
{
return dfn[u]<dfn[v]?u:v;
}
我晕。
- ST 表建表写错
for(int j=1;(1<<j)<=N;++j)
{
for(int i=1;i+(1<<j)-1<=N;++i)
{
stlca[j][i]=deepget(stlca[j-1][i],stlca[j-1][i+(1<<j/*应为1<<(j-1)!*/)]);
}
}
我怎么会在前面的 log 下标填
j-1后填了个i+(1<<j)。
- lca 求解过程中忘了写
u==v的情况。 - lca 求解过程中忘了将 $dfn$ 较大的 $u$ 与 $v$ 交换。
这两种情况倒是没写错过，不过以防万一还是加上。
- 直接把 lcason 返回。
st 表求的是 dfs 序中 $u$ 所在位置加上 $1$ 到 $v$ 的位置中的深度最小的节点，并不是 lca，而是 lca 的孩子。
- 左移与加法运算的时候不加括号。
stlca[j][i]=deepget(stlca[j-1][i],stlca[j-1][i+1<<(j-1)]);
左移的优先级小于加法，不加括号导致运算的顺序错误，建议多加括号保险
一些问题
- 我的 $k$ 在求解过程中写错了，原本应该是下面的代码的前者（
dfn[u]+1到dfn[v]这个序列的长度），却写成了后者（序列长度减去 $1$），但是没有被 hack 掉，是怎么回事？
int k=LOG2[dfn[v]-dfn[u]];//前者
int k=LOG2[dfn[v]-(dfn[u]+1)];//后者
可以看出这两种写法有区别当且仅当
dfn[v]-dfn[u]为 $2$ 的倍数。
此时两种写法虽然 log 下标不同，但可以看出其覆盖范围是相同的。
看的出来，后者写法的两段区间刚好无缝衔接（衔接的两个端点差为 $1$），所以两种写法的输出都是正确的。
后言
写的可能不是很完整，以后可能补充。