吼,最近真的忙
我感到非常抱歉的是我断更了ww(因为最近学校一堆烂事,真的是抽不出身子www
望各位神犇理解ww(WA^感谢~
言归正传
关于“树殓刨坟求LCA”,本蒟蒻总结了这个板子(真的是保姆级),望有所帮助趴hh
void dfs(int x,int fx)//第一遍dfs,扫出基本的父节点,深度,子树大小,重儿子等信息
{
f[x]=fx;
siz[x]++;
dep[x]=dep[fx]+1;
int maxx=0,maxp=0;
for(int i=head[x];i!=-1;i=edge[i].next)
{
int to=edge[i].to;
if(to==fx)
{
continue;
}
dfs(to,x);
siz[x]+=siz[to];
if(siz[to]>maxx)
{
maxx=siz[to];
maxp=to;
}
}
son[x]=maxp;
}
void dfs2(int x,int fx,int ffx)//第二遍dfs,扫出链顶,处理出每条链
{
top[x]=ffx;
if(son[x]==0)
{
return ;
}
dfs2(son[x],x,ffx);
for(int i=head[x];i!=-1;i=edge[i].next)
{
int to=edge[i].to;
if(to==son[x]||to==fx)
{
continue;
}
dfs2(to,x,to);
}
}
int LCA(int x,int y)//LCA
{
while(top[x]!=top[y])//两者不在同一条重链上
{
int tempa=top[x];
int tempb=top[y];//找出两个链顶
if(dep[tempa]<dep[tempb])
{
swap(tempa,tempb);
swap(x,y);
}
x=f[top[x]];
}
return dep[x]<dep[y]?x:y;
}
%%%
Www
,我弱的一批
代码缩进感人。
嘿,我从我们学校oj的编译器copy过来的(也许就这样qwq
抱歉啊