AcWing 846. 树的重心
原题链接
简单
作者:
fromthetop
,
2020-02-02 13:12:51
,
所有人可见
,
阅读 668
#这个奇妙写法可能只有我自己看得懂
#用数组模拟树的dfs()的粗浅理解,仅供参考
int n;
int h[N],e[M],ne[M],idx;
h[]是头节点最后一个加入了链表的真正地址集合,沿着h[i]的ne[i]遍历到-1就是把i有关的点都遍历一遍。
和单链表有点区别
e[]是下个连接节点下标的值
ne[]是通向该连通区域头节点的值,ne[]里实际上是地址
h[]是存储的地址,里面装的是idx
add()相当于在a链前面接上一个内容是b的节点,这个节点的地址是idx,内容用e[]装,里面是b
ne[idx]把他连到h[a]这个头上,然后把新头就变成这个点idx,idx自然++
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
一开始是要把h[]表初始化memset(h,-1,sizeof h)
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(st[j]) continue;
int s=dfs(j);
size=max(size,s);
sum+=s;
}
bool st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int dfs(int u)
{
st[u]=true;
int size=0,sum=0;
for(int i=h[u];i!=-1;i=ne[i])
{
int j=e[i];
if(st[j]) continue;
int s=dfs(j);
size = max(size,s);
sum+=s;
}
size = max(size,n-sum-1); //因为树不会往上走,所以要用一个n-sum-1去算出回不去的那些点有多少个
ans = min(ans,size);
return sum+1;
}