树的重心与直径.ppt

树的重心算法分析：
建立边表data。由于是无向的，因此边表长度为(N-1)*2。边表按照p1端点递增的顺序排序，以便计算每一个顶点的边表序号
树的基本操作:以结点1为根，计算出每个结点所在的子树的结点数。
枚举每一个结点，若将其删掉，那么考虑剩余的所有连通分量。
1、它的子树，其结点数可以直接调用。
2、它的上方子树，其结点数可通过n-1-减去所有子树的结点数算出。
这样，在其中选择d(i)最小的即可。时间复杂度：O(N)，空间复杂度：O(N)voiddfs(inti){
intj,k;
j=last[i];
size[i]=1;
while(j!=0){
k=other[j];
if(k!=father[i]){
father[k]=i;
dfs(k);
size[i]+=size[k];
if(ans[i]<size[k])ans[i]=size[k];
}
j=pre[j];
}
if(n-size[i]>ans[i])ans[i]=n-size[i];
return;
}树的直径原理:设起点为u,第一次BFS找到的终点v一定是树的直径的一个端点
证明:1)如果u是直径上的点，则v显然是直径的终点(因为如果v不是的话，则必定存在另一个点w使得u到w的距离更长，则于BFS找到了v矛盾)
2)如果u不是直径上的点，则u到v必然于树的直径相交(反证),那么交点到v必然就是直径的后半段了
所以v一定是直径的一个端点，所以从v进行BFS得到的一定是直径长度