C++树形结构(总）

一.基础：

1.概念：

2.定义：

Ⅰ.树的相关基础术语：

Ⅱ.树的层次：

3.树的性质：

二.存储思路：

1.结构体存储：

2.数组存储：

三.树的遍历模板：

四.信息统计方式：

1.自顶向下统计：

2.自底向上统计

五.基础练习：

六.树，进阶：

（1）.树的直径：

1.定义：

2.直径的性质：

3.树的直径求解方法：

4.直径端点求解方法：

朴素方法：

优化方法：

5.例题：

6.直径公共点：

7.例题：

8.去掉再加上：

9.例题：

（2）.树的中心：

1.树的概念：

2.树的性质：

3.树的中心求解：

4.例题：

（3）.树的重心：

1.基础概念：

2.求解方法：

3.例题：

4.重心的性质：

性质1：

性质2：

性质3：

性质4：

性质5：

5.例题：

①子树的重心

②唯一的重心

③会议

七.总结

一.基础：

1.概念：

在前面学过的存放数据的容器有：数组、链表、栈、队列等，这些都是线性结构，数据元素之间存在一对一的线性关系。但在实际生活中，往往是非线性关系，数据元素之间的关系通常可以一对多。所以必须要把这些数据关系储存下来。其实树形结构就像递归数一样。递归树中，都只能从父节点走到子节点。我们只需要记录每个父节点有哪些子节点，那么就可以遍历整个递归树。我们可以用动态数组(vector)来记录每个节点的子节点。这就是树的孩子表示法

2.定义：

Ⅰ.树的相关基础术语：

（1）.根节点：最顶层的节点就是根结点，它是整棵树的源头，一般用root表示。如1

（2）叶子节点：在树最底端的节点，就是其子节点个数为0的节点。如4、7、6、3

（3）.节点的度：指定节点有子节点的个数。如2的度为3

（4）.无根树：没有指定根节点的树，树的形态多样。明显这里以1为根和以5为根，树的形态不一样。

（5）.有根树：指定了根节点的树，树的形态唯一。

（6）.森林：由多棵树构成

（7）.链长：边权相加。

Ⅱ.树的层次：

（1）.节点高度：指从这个节点到叶子节点的距离（一共经历了几个节点）。

（2）.树的高度：指所有节点高度的最大值。

（3）.节点的层：从根节点开始，假设根节点为第1层，根节点的子节点为第2层，依此类推

3.树的性质：

性质1：n个节点，保证任意两点有且仅有一条路径，树中有且仅有n-1条边。

证明：除第一个节点外，连接一个其他节点，至少增加一条边，所以n个点至少要用n-1条边才能保证所有节点连通。若此时再增加一条非重边，任意两点间是否还存在一条唯一路径。

性质2：树的根结点没有前驱(父节点)，除根结点外的所有结点有且只有一个前驱。树中所有结点可以有零个或多个后继(子节点)。

证明：同上。

二.存储思路：

输入一个数字n表示一颗有n个点的树。接下来一行输入n个数，表示每个点上的权值ai。后面n-1行，每行输入三个数u,v,w，表示节点u,v存在一条边，边权为w。请把所有信息保存下来。

1.结构体存储：

用结构体把每个节点的信息进行封装。这样的优点在于节点信息非常独立，但是所占空间稍大。

struct node{int data;vector<int> v,w;
}a[105];
int main(){cin>>n;for(int i=1;i<+n;i++) cin>>a[i].data;for(int i=1;i<=n;i++){int x,y,z;cin>>x>>y>>z;a[x].v.push_back(y);a[y].v.push_back(x);a[x].w.push_back(z);a[y].w.push_back(z);}
}

2.数组存储：

用多个数组，分别描述每个节点的对应信息。这种方式的有点在于速度稍快，写起来简单。

int data[105]
vector<int> v,w;
int main(){cin>>n;for(int i=1;i<=n;i++) cin>>data[i];for(int i=1;i<=n;i++){int x,y,z;cin>>x>>y>>z;v[x].push_back(y);v[y].push_back(x);w[x].push_back(z);w[y].push_back(z);}
}

三.树的遍历模板：

我们可以发现前两道例题都是有向的边，所以不担心会从子节点重新走到父亲节点。但是通常来讲，树的边都是双向的我们在遍历的时候不希望一个点遍历多次。我们可以用dfs中记录由父亲节点(来向)，这样可以阻止走回去。

void dfs(int x,int fa){for(int i=0;i<v[x].size();i++){int y=v[x][i];if(x==fa) continue;dfs(y,x);}
}

四.信息统计方式：

1.自顶向下统计：

操作方法：在进入dfs之前进行信息统计。如求链长：树上两个节点必然有且仅有一条路径，我们可以把该路径看成一条链。路径上的边权和为两点的链长。

计算有根树中任意点到根节点的距离

int data[105];
void dfs(int x,int fa) {for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];dfs(y,x);}
}

扩展：输出有根树最长链的路径

在dfs时进行路径记录，用pre数组记录当前节点是由哪一个父亲节点走过来。
当找到最长链的终点，根据每个节点只有一个父亲。倒着找回去，就能输出完整路径。

int data[105]，pre[105];
void dfs(int x,int fa) {for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];dfs(y,x);}
}
void print(int x){vector<int> r;for(int i=x;i>0;i=pre[i]) r.push_back(i);for(int i=r.size()-1;i>=0;i--) cout<<i<<" ";
}

2.自底向上统计

操作方法：在dfs回溯之时进行信息统计。如求树的节点个数：当前树上共有多少个节点。

子树的概念：抹除当前根节点以及所有与根节点的连边后，产生的树都是当前根节点的子树。
如当前根节点1的子树有，以2、3、4为根的子树。

计算有根树中各子树的节点个数：

int data[105];
void dfs(int x,int fa) {data[x]=1;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;dfs(y,x);data[x]+=data[y];}
}

五.基础练习：

题目：

给定一棵有n个点的树（结点个数≤100），指定根节点为1。每个点带有点权。求以1为根节点的最大子树大小，以及最大影响力。影响力=该点权*该点向下的最大子树（这里的子树不包括从根节点来的部分）。

题目分析：

先用dfs求出每个各点的为根的节点个数(子树大小)，用sz数组进行保存，并且在整个回溯过程中，不断比较节点1相连的几颗子树，求取最大值。

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,data[1001],s[1145],maxn;//data数组记录以i为根的子树大小
vector<int> v[105];
vector<int> w[105];
void dfs(int x,int fa){s[x]=1;for(int i=0;i<v[x].size();i++){int y=v[x][i];if(y==fa) continue;dfs(y,x);s[x]+=s[y];//记录点权相加maxn=max(s[y],maxn);//打擂台求最大}
}
int main() {cin>>n;for(int i=1;i<=n;i++) cin>>data[i];for(int i=1; i<n; i++) {int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}dfs(1,0);cout<<maxn<<" ";maxn=0; for(int i=1;i<=n;i++){maxn=max(s[i]*data[i],maxn);//打擂台求最大影响力}cout<<maxn;return 0;
}

六.树，进阶：

（1）.树的直径：

1.定义：

树的直径是树上两点间距离的最大值。即树中最远的两个节点之间的距离被称为树的直径，连接这两点的路径被称为树的最长链

最长链：4-2-1-7-6-3

所以这颗树的直径是15，直径路径为4-2-1-3-6

2.直径的性质：

直径的性质1：直径的端点一定是叶子节点

直径的性质2：任意点的最长链端点一定是直径端点

直径的性质3：如果一棵树有多条直径且边权都为正，那么它们必然相交，且有极长连续段（可以是一个点，交点为树的中心）

直径的性质4：树T1的直径为x,y，树T2的直径为s,t。现有一边u,v与两颗树相连，新树的直径端点一点是x,y,s,t中的两个

3.树的直径求解方法：

引理性质2：任意点的最长链端点一定是直径端点。方法：我们随意找一个点x,进行dfs找到最长链的端点s,再以端点s做第二遍dfs，此时可以找到直径的第二个端点t。此时端点s到t的距离就是树的直径。

输入一颗无根树，第一行为一个正整数n(n<1e5),表示这颗树有n个节点接下来的n−1行,每行三个正整数u,v,w，表示u,v（u,v<=n）有一条权值为w(w<100)的边相连，求树的直径。

#include<bits/stdc++.h>
using namespace std;
int n,data[100005],pl,maxn;
vector<int> v[100005];
vector<int> w[100005];
void dfs(int x,int fa) {for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];if(data[y]>maxn) maxn=data[y],pl=y;//记录端点dfs(y,x);}
}
int main() {cin>>n;for(int i=1; i<n; i++) {int x,y,z;cin>>x>>y>>z;v[x].push_back(y);v[y].push_back(x);w[x].push_back(z);w[y].push_back(z);}dfs(1,0);//寻找直径memset(data,0,sizeof data);//清空距离dfs(pl,0);//从pl出发寻找端点cout<<maxn;return 0;
}

4.直径端点求解方法：

我们通过记录父亲节点的方式能够把直径上的所有点全部记录下来。在树中，直径端点是常用点(假设端点为s,t)，我们树上任意一点p所能到的最大距离，只有可能是到ps或pt

那如何找到所有点到两个直径端点的距离？

朴素方法：

求出直径端点后，以每个点为根做dfs，找到根节点到端点的距离。复杂度O(N2)。

优化方法：

第一次从任意点出发，必然能到达直径的一个端点s。第二次从s点进行dfs找到端点t，此时记录所有点到s的距离。第三次从t点进行dfs，记录所有点到t的距离。复杂度：O(n)

5.例题：

题目描述：

输入一颗无根树，第一行为一个正整数n(n<1e5),表示这颗树有n个节点接下来的n−1行,每行三个正整数u,v,w，表示u,v（u,v<=n）有一条权值为w(w<100)的边相连，输出各个点到左右端点的距离。(默认左端点为编号小的点，右端点为编号大的点。)

题目分析：

我们需要多次求树的直径。通过第一次dfs从根寻找第一个端点pl，再通过第二次dfs从pl寻找第二个端点pr，并记录所经过的距离，最后通过第三次dfs记录每个点到左右端点的距离。多次求树的直径，有很多重复操作，包括清空最长链长度，以及重置距离数组，我们可以放到循环中，这样就不容易遗忘初始化。同时我们还可以记录当前是第几次dfs，到指定次数dfs时才更新信息。

正确代码：

#include <bits/stdc++.h>
using namespace std;
vector <int> v[100002];
vector<int> w[100002];
int n,maxn,sum,data[100002],dl[100002],s[100002],l,r;
void dfs1(int x,int fa) {if(data[x]>maxn) maxn=data[x],sum=x;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];dfs1(y,x);}
}
void dfs2(int x,int fa) {dl[x]=data[x];if(data[x]>maxn) maxn=data[x],sum=x;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];dfs2(y,x);}
}
void dfs3(int x,int fa) {s[x]=data[x];if(data[x]>maxn) maxn=data[x],sum=x;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];dfs3(y,x);}
}
int main() {cin>> n;for(int i=1; i<n; i++) {int x,y,z;cin>>x>>y>>z;v[x].push_back(y);v[y].push_back(x);w[x].push_back(z);w[y].push_back(z);}dfs1(1,0);memset(data,0,sizeof data);maxn=0,l=sum;dfs2(l,0);memset(data,0,sizeof data);maxn=0,r=sum;dfs3(r,0);if(l>r) swap(dl,s),swap(l,r);//保证做端点较小for(int i=1; i<=n; i++) cout<<i<<" "<<dl[i]<<" "<<s[i]<<endl;return 0;
}

6.直径公共点：

以当一颗树存在多条直径时，引理性质3，公共边一定连续，因此可以直接对公共点/边进行求解

公共点公共边的求法：

找到直径左右端点s,t，从左往右遍历直径上的点进行dfs，如果某点r在直径外找到一点与到右端点t距离相同，点r右边的点一定不是公共点。同理，从右往左遍历直径上的点进行dfs，如果某点l在直径外找到一点与到左端点s距离相同，l左边的点一定不是公共点。此时，l->r就是我们直径的公共点。因此我们只需要找到公共点边界l,r即可。使得l尽可能靠右，r尽可能靠左。

7.例题：

题目描述：

给定一棵树，树中包含 n（n<=1e5）个结点（编号1~n）和 n−1 条无向边，每条点都有一个权值c（1<=c<=100）。请找出所有直径的公共点权值和。(第一个点权值为0)

题目分析：

按照直径公共点求解的方法进行操作。

1.找到直径左右端点lp,rp;

2.找到直径上的点x到左端点lp的距离ld[x]，到右端点rp的距离rd[x];

3.找到直径上的点x到非直径点(且不通过直径点)的距离dis[x]

4.从直径左端点开始向右端点扫描，如果dis[i]=rd[i]，则停下，找到公共点右区间r=i

5.从直径右端点开始向左端点扫描，如果dis[j]=ld[j]，则停下，找到公共点左区间l=j

6.计算直径上i到j的点权和得出答案。

真确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2E5+5;
int n,c[N];
vector<int> v[N];
int dl[N],dr[N],d[N],dis[N];//记录各点距离信息
int pre[N],a[N],vis[N],tot,maxn,t,pl,pr,l,r;//记录直径上的信息
bool flag;
void dfs(int x,int fa,int cnt) {if(cnt==3) pre[x]=fa;//记录直径路径for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;d[y]=d[x]+1;if(maxn<d[y]) maxn=d[y],t=y;if(cnt==2) dl[y]=d[y];if(cnt==3) dr[y]=d[y];dfs(y,x,cnt);}
}
void dfs2(int x,int fa) {for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa || vis[y]==1) continue;dfs2(y,x);dis[x]=max(dis[x],dis[y]+1);}
}int main() {cin>>n;for(int i=1; i<n; i++) {int x,y,z;cin>>x>>y>>z;v[x].push_back(y);v[y].push_back(x);c[i+1]=z;}t=1;for(int i=1; i<=3; i++) {//进行3次dfsmaxn=0;memset(d,0,sizeof d);dfs(t,0,i);if(i==1) pl=t;//获取直径的左端点if(i==2) pr=t;//获取直径的右端点}for(int i=t; i; i=pre[i]) {vis[i]=1;a[++tot]=i;//从左到右标记直径上的点}for(int i=2; i<tot; i++) dfs2(a[i],0);//获取点x能到的不在直径上的最远点l=a[1],r=a[tot];//使得右端点r靠左，左端点l靠右for(int i=2; i<tot; i++) {int x=a[i];if(dis[x]==dr[x] && flag==false){r=x;flag=true;}if(dis[x]==dl[x]) l=x;}if(l==a[1]&&r==a[tot]) {//没有公共点cout<<0;return 0;}int ans=c[r];while(l!=r) ans+=c[l],l=pre[l];cout<<ans;return 0;
}

8.去掉再加上：

性质4分析：

uv连接后有两种情况1.新直径不过uv，即现直径为st或为xy。2.新直径过uv，则现直径为max(vs,vt)+max(ux,uy)+uv。这两种情况都能保证新直径端点为x,y,s,t中的任意两个。新直径为以上三个中最大值。

连边uv求新树直径最小：

引理性质4可知：

st与xy不变，此时只能减下过uv的直径大小。以max(vs,vt)为例，要使该值最小，则v应当在树的中心位置，这样vs与vt越均衡。同理u也应该在T2的树的中心位置。

连边uv求新树直径最大：与前面一致，以max(vs,vt)为例，要使得该值最大，则v应当选择直径端点位置。因此uv选择各自直径的端点位置时，直径最大。

9.例题：

题目描述：

给定一棵 n (1<=n<=1e4)个点构成的树。树中每条边的长度均为 1。现在，需要你去掉树中的一条边，然后再给树加上一条边，使得图形仍是树。请计算，新树的直径的最小可能值。(新树可以和原来的树完全一样)。

题目分析：

由性质4，我们知道连接时需要连接两棵树的中心，才能使得新树直径尽可能小。所以连接点很好处理。对于断开点，我们必然只有断开直径上的边，否则直径不可能变小，具体直径上哪一条边，我们可以进行枚举。

真确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1E4+5;
vector<int>v[N];
int n,ans,maxn,t,pre[N],d[N];
bool vis[N][N];
void dfs(int x,int fa,int cnt,int k) {if(cnt==2&&k==0) pre[x]=fa;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa||vis[x][y]) continue;d[y]=d[x]+1;if(d[y]>=maxn) maxn=d[y],t=y;dfs(y,x,cnt,k);}
}
int get(int x,int k) {t=x;for(int i=1; i<=2; i++) {maxn=0;memset(d,0,sizeof d);dfs(t,0,i,k);}return maxn;
}
int main() {cin>>n;for(int i=1; i<n; i++) {int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}ans=get(1,0);int ans=maxn,res;for(int i=t; i; i=pre[i]) {if(i==0||pre[i]==0) continue;vis[i][pre[i]]=vis[pre[i]][i]=1;int lena=get(i,1),lenb=get(pre[i],1);res=max(max(lena,lenb),(lena+1)/2+(lenb+1)/2+1);ans=min(ans,res);res=0;vis[i][pre[i]]=vis[pre[i]][i]=0;}cout<<ans;return 0;
}

（2）.树的中心：

除了直径的端点还有一个点我们完成题目时经常会用到，这就是树的中心。

1.树的概念：

以树的中心为根时，从该根到每个叶子节点的最长路径最短，使得路径和平衡。实际应用：在若干村庄中（树形结构）修一个小学，使得所有村庄到学校的最大距离最小，小学应该修在什么位置？

2.树的性质：

性质1：树的中心一定在直径上，且趋向于中点位置

性质2：树的中心可以有一个(单中心)，也可以有两个(双中心)

证明：引理性质2，若树的中心p不在直径st上，st上有一点q与直径联通。中心点能到的最远距离为：max(qs,qt)+pq，若要使得该值最小，pq应当为0，因此p在直径上。同时为了让max(qs,qt)更小，树的中心要在直径中点处。

3.树的中心求解：

我们现在已经知道求解任意一点到两端点的距离，即根据性质2可很轻松得到每个点能到的最长路径。求出每个点后的路径后，一次遍历便可知树的中心点。

4.例题：

题目描述：

给定一棵树，树中包含 n个结点（编号1~n）和 n−1 条无向边，每条边都有一个正权值。请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。输出该节点以及最近距离。(若存在多个点的距离相同，则输出编号较小的一个)

题目分析：

有data数组表述每个点出发的最大距离，因此我们在第2次和第3次dfs的过程中，与dis数组比较即可。并且在第3次dfs时，把最小距离求出来。

正确代码：

#include<bits/stdc++.h>
using namespace std;
int n,data[100001],dl[100001],maxn,maxn2,minn=2e9,tmp,pl;
vector<int> v[10001];
vector<int> w[10001];
void dfs(int x,int fa,int cnt) {for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;data[y]=data[x]+w[x][i];if(maxn<data[y]) pl=y,maxn=data[y];if(cnt==3) {maxn2=max(data[y],dl[y]);if(maxn2<minn) minn=maxn2,tmp=y;}dfs(y,x,cnt);}
}
int main() {cin>>n;for(int i=1; i<=n-1; i++) {int x,y,z;cin>>x>>y>>z;v[x].push_back(y);v[y].push_back(x);w[x].push_back(z);w[y].push_back(z);}dfs(1,0,1);maxn=0;memset(data,0,sizeof data);dfs(pl,0,2);for(int i=1; i<=n; i++)	dl[i]=data[i];memset(data,0,sizeof data);maxn=0;dfs(pl,0,3);cout<<tmp<<" "<<minn;return 0;
}

（3）.树的重心：

1.基础概念：

使得最大子树大小最小。那么这个点叫就被叫做树的重心

在线性的序列[1,n]中，我们在考虑用分治思想处理问题时，需对问题进行划分。在划分问题时若要更加均匀，我们选择中点mid可以更加高效。这样得到[1,mid],[mid+1,n]两个子序列，因为子序列中元素的个数<=n/2(向上取整)，这样可以把问题复杂度优化到O(logn)

2.求解方法：

显然，要求树的重心，我们可以枚举出每个点为断点时，所产生的最大子树大小。某断点求当前最大子树大小的方法：对该点进行dfs，找到以i为根节点的子树的大小记录到sz[i]中，接着在该点的儿子中找si最大的一个。复杂度为O(n2)

3.例题：

题目描述：

给定一棵树，树中包含 n（n<=1e5）个结点（编号1~n）和 n−1 条无向边，找出树的重心若重心不止一个，则输出编号较小的），以及当前重心下的最大子树大小。

题目分析：

这是一道关于重心的基础题，仅需用重心的求解方法，再用之前讲的求最大子树的方法就可以了。

正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
vector<int> v[N];
int d[N],minn=N,n;//d数组记录当前节点子树的大小
int res,id;//id记录重心，minn为重心下最大子树的大小
void dfs(int x,int fa) {d[x]=1;int res=0;//开始找以x为根的最大子树for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;dfs(y,x);d[x]+=d[y];res=max(d[y],res);//打擂台找几个子树中的最大值}res=max(res,n-d[x]);//除最大字数为，剩下的子树if(minn>res) minn=res,id=x;
}
int main() {cin>>n;for(int i=1; i<n; i++) {int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}dfs(n,0);cout<<id<<" "<<minn;return 0;
}

4.重心的性质：

设mss(u)表示以u为重心的最大子树，s0(u)表示以u为根的子树大小,su(v)表示以u为根的的子树v大小。

性质1：

重心点的最大子树大小不大于整棵树大小的一半。

证明：

设u为重心，v为u的最大子树。可以得出：s0[u]-su[v]>=su[v] ，即 su[v]<=s0[u]/2在整颗树中，存在s0[u]=n，所以su[v]<=n/2得证以某点为根，最大子树大小不超过n/2的都是树的重心

常用推导：

Ⅰ.以某点为根，最大子树大小不超过n/2的一定是树的重心。

Ⅱ.以root为根的有根树中，树的重心一定在其最大的一颗子树内。具体来讲，假设y为root的最大子树的儿子，那么重心一定在tp[y]->root的这一条链中（tp[y]表示子树y的重心）。

性质2：

非空树有且仅有1-2个重心。当有两个重心时，树定有偶数个节点，且两个重心相邻。

证明：

假设u、v为树上两个重心，u，v分别为对方最长链上的点。此时：mss[u]=mss[v]又设k为两个重心之间存在的点数。由mss[u]=su[v]+k，mss[v]=sv[u]+k,推出sv[u]=su[v]。在k个点中选择中点p，此时，mss[p]=max(su[v]+k/2,sv[u]+k/2) >=su[v]+k,当且仅当k=0时，不等式成立。重心u、v之间必不可能有点。所以若有两个重心，则重心必然相邻。

性质3：

树中所有点到重心的距离和最小，反过来距离和最小的点一定是重心。

证明：

当前重心为u。mss[u]=su[v]。假设重心从u移动到v，mss[v]=sv[u]，可得1类节点到重心的距离加1，2类节点到重心的距离减少1，因此当增加部分sv[u] 小于减少部分 sv[u]时，距离和减少所以当su[v]>sv[u]时，重心移动，得到mss更小。反之若当前mss已经最小，则无法再产生一个更小距离和。

性质4：

往树上增加或减少一个叶子，如果原节点数是奇数，那么重心可能增加一个，原重心仍是重心；如果原点数是偶数，重心可能减少一个，另一个重心仍是重心。节

性质5：

把两棵树通过一条边相连得到一棵新的树，则新的重心在较大的一棵树一侧的连接点与原重心之间的简单路径上。如果两棵树大小一样，则重心就是两个连接点。

5.例题：

①子树的重心

题目描述：

输入一棵树,判断每一棵子树的重心是哪一个节点。第一行输入n,q。n表示树的节点个数，q表示询问次数。第二行n-1个数，分别表示从节点2开始，各节点的父亲节点。后面q行，每行一个数x，表示询问当前以x为根的子树中，树的重心位置。(n,q<=3e5)

题目分析：

本题若对每一次询问都查询一遍子树的重心，那么复杂度为O(nq)。在我们求一颗树T的重心时，根据推导2知道，重心一定在最大子树的重心到该树T的根这一条链上。所以我们如果知道最大子树的重心，此时就可以遍历这一条链上的点，根据推导1，只要该点满足其最大子树大小不超过n/2，那么一定是重心。所以我们可以dfs下去，先求出小的子树重心，回溯时再把当前的重心进行记录即可。复杂度O(n+q)

正确代码：

②唯一的重心

题目描述：

给定一棵节点数为 n(n<=3e5) 的树，删一条边然后加上一条边，使得该树的重心唯一。（删掉的边和加上的边可以是同一条）输出删边与加边信息，本题多测。

题目分析：

若存在一个重心，删边与加边都可以是同一条边。若不止一个重心，引理性质2，最多存在两个重心，且重心直接相连。假设两重心分别为idx，idy。要保证只留下一个重心，那就应当对某个重心子树idx进行修改，删除其叶子节点的一条边，且将该叶子节点直接连到另一个重心idy上即可。

正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,minn=N,z1,z2;//z1、z2两个重心
int u,sz[N],f[N];//u是断开的叶子节点
vector<int>v[N];
void dfs(int x,int fa) {sz[x]=1,f[x]=fa;int res=0;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;sz[x]+=sz[y];res=max(res,sz[y]);}res=max(res,n-sz[x]);if(minn>res) z1=x,z2=0,minn=res;else if(minn==res) z2=x;
}
void dfs1(int x,int fa) {if(v[x].size()==1) u=x;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fa) continue;dfs1(y,x);}
}
int main() {int t;cin>>t;while(t--) {cin>>n;for(int i=1; i<n; i++) {int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}dfs(1,0);if(z2==0) {//只有一个重心，就直接输出cout<<"1 "<<v[1][0]<<endl<<"1 "<<v[1][0]<<endl;continue;}if(f[z1]!=z2) swap(z1,z2);//保证只有一个重心在子树上遍历dfs1(z1,z2);cout<<u<<" "<<f[u]<<endl<<u<<" "<<z2<<endl;for(int i=1; i<=n; i++) {f[i]=0,v[i].clear();}minn=N,z1=z2=0;}return 0;
}

③会议

题目描述：

有一个村庄居住着 n 个村民，有 n−1 条路径使得这 n 个村民的家联通，每条路径的长度都为 1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

题目分析：

求所有点到某点的距离和，根据重心性质3，显然是到重心最小，因此求出重心，在进行距离和统计即可。

正确代码：

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,minn=N,idx,idy,sum,u,sz[N];//sz数组记录当前节点的子树大小
vector<int>v[N];
void dfs(int x,int fat) {sz[x]=1;int res=0;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fat) continue;dfs(y,x);sz[x]+=sz[y];res=max(sz[y],res);}res=max(res,n-sz[x]);if(minn>res) idx=x,minn=res;else if(minn==res&&idx>x) idx=x;
}
void dfs1(int x,int fat,int num) {sum+=num;for(int i=0; i<v[x].size(); i++) {int y=v[x][i];if(y==fat) continue;dfs1(y,x,num+1);}
}
int main() {cin>>n;for(int i=1; i<n; i++) {int x,y;cin>>x>>y;v[x].push_back(y);v[y].push_back(x);}dfs(1,0);//找重心dfs1(idx,0,0);//统计距离和cout<<idx<<" "<<sum;return 0;
}