关于树剖的一个很小的问题
查看原帖
关于树剖的一个很小的问题
526895
WYZ20030051楼主2023/7/28 09:00

第一次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] 的时候写的不一样

2023/7/28 09:00
加载中...