树的直径
定义
那么树上最远的两个点，他们之间的距离，就被称之为树的直径。
树的直径的性质
1. 直径两端点一定是两个叶子节点。
2. 距离任意点最远的点一定是直径的一个端点，这个基于贪心求直径方法的正确性 可以得出。
3. 对于两棵树，如果第一棵树直径两端点为(u,v)，第二棵树直径两端点为 (x,y)，用条边将两棵树连接，那么新树的直径一定是u,v,x,y中的两个点。
4. 对于一棵树，如果在一个点上接一个叶子节点，那么最多会改变直径的一个端 点。
5. 若一棵树存在多条直径，那么这些直径交于一点且交点是这些直径的中点。
树的直径的求法
解法1：树型DP
直接上代码：
void dp(int x,int fa){//f[i]表示以i为根节点的最长链
for(int i=head[x];i;i=e[i].next){
int y=e[i].v;
if(y==fa) continue;//防止死循环
dp(y,x);
ans=max(ans,f[x]+f[y]+e[i].w);//更新最长链+次长链的长度
f[x]=max(f[x],f[y]+e[i].w);//更新f[x]的长度
}
}
树形DP有一些难理解，但他可以解决负边权的问题
解法2：两次dfs/bfs
上代码：
void dfs(int x,int fa){//dis[i]表示以i的最长距离
if(dis[x]>ans){
ans=dis[x];//更新
p=x;//记录最远的点，因为要两次dfs才能确定直径
}
for(int i=head[x];i;i=e[i].next){
int y=e[i].v;
if(y==fa)continue;
dis[y]=dis[x]+e[i].w;//计算最长距离
dfs(y,x);
}
}
解法2运用了性质2，易理解，但不能处理负边权问题。
上一道例题：https://www.luogu.com.cn/problem/P3629
AC代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,k;
int a,b;
int p;
int idx=1;
int head[N];
int dis[N];
int pass[N];
int f[N];
int ans=0; struct node{
int v;
int next;
int w;
}e[N*2]; void add(int a,int b){
e[++idx].v=b;
e[idx].next=head[a];
e[idx].w=1;
head[a]=idx;
} void dfs(int x,int fa){
if(dis[x]>ans){
ans=dis[x];
p=x;
}
for(int i=head[x];i;i=e[i].next){
int y=e[i].v;
if(y==fa)continue;
dis[y]=dis[x]+e[i].w;
pass[y]=i;
dfs(y,x);
}
} void dp(int x,int fa){
for(int i=head[x];i;i=e[i].next){
int y=e[i].v;
if(y==fa) continue;
dp(y,x);
ans=max(ans,f[x]+f[y]+e[i].w);
f[x]=max(f[x],f[y]+e[i].w);
}
} int main(){
cin>>n>>k;
for(int i=1;i<n;i++){
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs(1,0);
memset(dis,0,sizeof(dis));
memset(pass,0,sizeof(pass));
ans=0;
dfs(p,0);
if(k==1){
cout<<2*(n-1)-ans+1;
return 0;
}
int l1=ans;
ans=0;
while(pass[p]){
e[pass[p]].w=-1;
e[pass[p]^1].w=-1;
p=e[pass[p]^1].v;
}
dp(1,0);
cout<<2*(n-1)-l1-ans+2;
return 0;
}
树的重心
定义
树的重心也叫树的质心。对于一棵 个节点的无根树，找到一个点，使得把树变成以该 点为根的有根树时，最大子树的结点数最小。换句话说，删除这个点后最大连通块（一定是 树）的结点数最小，删去重心后，生成的多棵树尽可能平衡。
性质
1. 树中所有点到某个点的距离和中，到重心的距离和是最小的，如果有两个重心， 他们的距离和一样。
2. 把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
3. 一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
4. 一棵树最多有两个重心，且相邻
思路
找到以i为根结点的最大子树大小，与现在最小最大子树相比较，不断更新找出重心
//minNode当前重心节点
//minBalance当前重心节点的最大子树节点个数
int d[maxn];
//d[i]表示以i为根的子树节点个数
void dfs(int u,int fa){
d[u]=1; //节点本身
int maxSub=0,size=tree[u].size(); //maxSub为节点u的最大子树节点个数
for(int i=0;i<size;i++){
int v=tree[u][i];
if(v!=fa){
dfs(v,u);
d[u]+=d[v];
maxSub=max(maxSub,d[v]);
}
}
maxSub=max(maxSub,n-d[u]);
if(maxSub<minBalance){
minNode=u;
minBalance=maxSub;
}
}