DFS序
一般与线段树等综合运用，就是将树转换为线段，存在线段树中
点击查看代码
void dfs(int now)
{
vis[now]=1;
a[++dfscnt]=x/shuzu[x];//用途线段树 if(l==r)st[rt].val=a[l]
in[x]=dfscnt;
for(int i=head[now];i;i=edge[i].next)
{
int to=edge[i].to;
if(!vis[to])
{
dfs(to);
}
}
out[now]=dfscnt;
}
ST表
\(i到i+2_{j-1}-1和i+2_{j-1}到i+2_j-1\)
注意j层循环在最外面，i层在里面
因为更新时i+(1<<(j-1))会有后效性
点击查看代码
void st()
{
for(int i=1;i<=len;i++)
{
f[i][0]=a[i];
}
for(int j=1;(1<<j)<=len;j++)
{
for(int i=1;i+(1<<j)-1<=len;i++)//i+(1<<j)-1表示从i开始(1<<j)-1个长度
{
f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
}
}
int query(int l,int r)
{
int k=0;
while((1<<(k+1))<=r-l+1)k++;
return min(f[l][k],f[r-(1<<k)+1][k]);
}
LCA
点击查看代码
int lca(int x,int y)
{
if(d[x]<d[y])swap(x,y);
for(int i=31;i>=0;i--)
{
if(d[f[x][i]]>=d[y])x=f[x][i];
}
if(x==y)return x;
// for(int i=0;i<=31;i++)
for(int i=31;i>=0;i--)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
DFS_init
点击查看代码
void dfs(int x,int fa)
{
d[x]=d[fa]+1;
f[x][0]=fa;
for(int i=head[x];i;i=edge[i].next)
{
int to=edge[i].to;
if(to==fa)continue;
dis[to]=dis[x]+edge[i].w;
dfs(to,x);
}
}
void dfs_init()//在DFS之后记得调用这个函数,血的教训
{
for(int j=1;j<30;j++)
{
for(int i=1;i<=n;i++)
{
f[i][j]=f[f[i][j-1]][j-1];
//dis[i][j]=min(dis[i][j-1],dis[f[i][j-1]][j-1]);
}
}
}
BFS_init
点击查看代码
void bfs()
{
q.push(1);vis[1]=1;d[1]=1;
while(q.size())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=edge[i].next)
{
int to=edge[i].to;
if(!vis[to])
{
q.push(to);vis[to]=1;
d[to]=d[u]+1;
f[to][0]=u;
for(int j=1;j<30;j++)f[to][j]=f[f[to][j-1]][j-1];
}
}
}
}