第一次dfs处理fa,son,size和dep的时候,为什么以下两种写法都能过呢?
第一种
void dfs1(int u,int fat)
{
dep[u]=dep[fat]+1;
fa[u]=fat;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fat)
continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
}
第二种
void dfs1(int u,int fat)
{
dep[u]=dep[fat]+1;
fa[u]=fat;
son[fa]=u;
siz[u]=1;
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(v==fat)
continue;
dfs1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
v=son[u];
}
}
二者只有更新 son[u] 的时候写的不一样