树的直径和重心

---

树的直径

模板题1 模板题2

定义

树中的两节点间最长距离

算法

（树形DP可，略）

简述为两遍DFS（BFS）：第一遍先从任意一个节点开始DFS，找到与它相连的最长的路径所对应的的节点（这个点一定是直径的一个端点），再从这个节点开始DFS，找到的最长路径就是树的直径（证明略。。其实很简单）

注意：两遍DFS之前需要初始化，否则会死的很惨

代码（很巧妙）

code

void dfs(int x,int fa,int len){
	for(int i=head[x];~i;i=e[i].next){
		int v=e[i].v,w=e[i].w;
		if(v==fa) continue;
		dfs(v,x,len+w);
		dis[v]=max(dis[v],len+w);
		if(len+w>=ans){
			ans=len+w;
			start=v;
		}
	}
}

int main(){
    dfs(1,-1,0);
	dfs(start,-1,0);
}

树的重心

模板题（这题需要按从小到大顺序输出树的每个重心）

定义

树的重心定义为一个节点，其所有的子树中最大的子树节点数最少

注意：一棵树可能有多个重心

算法

树形DP的思想

任取一个节点开始DFS，递归遍历它的一颗子树，记录它本身x以及它的父节点fa，DFS过程中只有当遍历到的节点不等于本身的父节点时才会继续递归（原因是防止死循环），递归求出这颗子树的节点数Size[v]，经过一轮遍历找出最大值更新给ans[x]，那么这个x对应的另一颗子树的节点数就是n-Size[x]，两者取最大值就是以这个节点为重心的最大子树的节点数

代码（求所有点为重心的最大子树节点数）

code

void dfs(int x,int fa){
    Size[x]=1;
    ans[x]=0;
    for(int i=head[x];~i;i=e[i].next){
        int v=e[i].v;
        if(v!=fa){
            dfs(v,x);
            Size[x]+=Size[v];
            ans[x]=max(ans[x],Size[v]);
        }
    }
    ans[x]=max(ans[x],n-Size[x]);
    if(ans[x]>maxh){ //maxh存最大子树节点数的最小值，即答案
        maxh=ans[x];
    }
}