#创作计划# 树的入门
2026-02-06 21:37:37
发布于：广东
持续更新中......
导言：
树作为一种在算法竞赛中十分重要的数据结构，也在图论方面有着重要作用，所以我想花一些时间讲一下关于树的知识。
1.树的性质与遍历：
这一部分较为简单，所以简单带过。
树是一种特殊的图，树必须连通。一颗个结点的树有条边。
如图，结点1和结点2为例，结点1被称为结点2的父结点，同时，结点2就是结点1的子结点。
结点1与结点2和结点4是同一个深度，所以被称为兄弟结点，结点1没有直接的上级，所以被称为根结点。再看到结点5他没有任何一个下属，像这样的结点就被称作叶子结点。
此外有根结点的树被称为有根树，自然，没有根结点的树就叫无根树了。
除了这些，还有一些比较重要的概念，比如结点5，从结点5的父结点开始一直到根结点经过的所有结点就称为该结点的祖先，同样，也会有后代这个概念，意思也就是把前面的反着来而已。
讲完基础概念了，现在可以说遍历了，一般使用 来遍历，也比较简单，如果不会的话，可以自学一下深度优先搜索算法，现在使用一道例题来带过。
:
思路分析：
按照题意添加双向边，然后遍历除了父结点外的边，然后计算深度，判断深度是否小于等于即可，是一道简单的基础题。
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
vector<int>vec[N];
int n,m,ans,d,dis[N];
void add(int u,int v){
vec[u].push_back(v);
vec[v].push_back(u);
}
void dfs(int u,int f){
if(dis[u]<=d) ans++;
for(int i=0;i<vec[u].size();i++){
int v=vec[u][i];
if(v==f) continue;
dis[v]=dis[u]+1;
dfs(v,u);
}
}
int main(){
cin>>n>>d;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
}
dfs(1,0);
cout<<ans-1;
return 0;
}
2.树的直径与重心：
导言：
树作为一种特殊的结构，其自身也具有一些特殊的性质来帮助解决一些树中的问题，这次将与树的重心与直径为例来求解问题。
树的直径（）:
定义：树中任意两个节点之间的最长路径的长度。
求解直径：
如何求解直径？最朴素的做法就是暴力枚举 的两个点然后每一个再跑一遍 就行了，可以是可以，但是 的时间复杂度还是逆如天，所以一个高效的 方法就出现了。
大概的思路就是跑两遍 来求解，接下来给出具体步骤。
（1）随意选择一个结点 作为起点，然后进行第一遍 ，同时记录下其他结点距离 的距离。遍历完之后，可以找到距离 最远的结点，将他记为 。
（2）将 作为起点，重复上述的操作，再次找到距离 距离最远的结点，记作 。
（3）此时 与 就是直径的两个端点。这样就求出了这棵树的一条直径。
证明比较复杂（实则是我太弱了），所以这里就不证明了，下面给出一道例题。
:
思路分析：
首先按照刚才两遍 的方法求出树的直径，然后在直径上找最优核，这里可以使用滑动窗口来高效解决，最后再计算非直径节点到直径的最大距离。
#include<bits/stdc++.h>
using namespace std;
#define MAXN 500007
int n,s,ans=MAXN*1000,far;
int dis[MAXN],fa[MAXN],flag[MAXN];
struct edge{
int to,w;
};
vector<edge>G[MAXN];
void dfs(int u,int f){
fa[u]=f;
if(dis[u]>dis[far]) far=u;
for(int i=0;i<G[u].size();i++){
int v=G[u][i].to,w=G[u][i].w;
if(v==f||flag[v]) continue;
dis[v]=dis[u]+w;
dfs(v,u);
}
}
int main(){
cin>>n>>s;
for(int i=0;i<n;i++){
int u,v,w;
cin>>u>>v>>w;
G[u].push_back(edge({v,w}));
G[v].push_back(edge({u,w}));
}
int A,B;
dis[1]=1;dfs(1,0);A=far;
dis[far]=0; dfs(far,0); B=far;
for(int i=B,j=B;i;i=fa[i]){
while(dis[j]-dis[i]>s) j=fa[j];
int x=max(dis[B]-dis[j],dis[i]);
ans=min(ans,x);
}
for(int i=B;i!=0;i=fa[i]) flag[i]=1;
for(int i=B;i!=0;i=fa[i]){
dis[i]=0;
dfs(i,fa[i]);
}
for(int i=1;i<=n;i++) ans=max(ans,dis[i]);
cout<<ans;
return 0;
}
树的重心（ ）:
定义：树的重心是树中的一个特殊节点，满足：将该节点移除后，剩余的各个连通子树的节点数量的最大值是所有节点中最小的。
树的重心的四个重要性质：
1.平衡性：删除重心后，剩余的每一棵子树的节点数都不超过原树总节点数的一半（≤ n/2）。
2.唯一性 / 相邻性：一棵树的重心最多有两个。如果存在两个重心，那么这两个节点一定是相邻的。
3.路径最优性：树中所有节点到重心的距离之和最小。若有两个重心，它们到所有节点的距离之和是相等的。
4.连通性：在一棵树上，所有的重心都位于同一条路径上。
找重心的方法：
1.任选根节点，用 DFS 算出每个节点的子树大小。
2.对每个节点，计算删除后最大连通块大小（子树最大值与父方向连通块取大）。
3.最大连通块最小的节点就是重心，最多两个且相邻。
:
思路分析：
就是关于树的重心，上面已经讲过了，但这里我使用的是 。
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
const int inf=0x7f7f7f7f;
int f[MAXN],size[MAXN],head[MAXN],dep[MAXN];
int n,center,sum=0;
vector<int>G[MAXN];
queue<int>q;
void get(int u,int fa){
size[u]=1,f[u]=0;
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
get(v,u);
size[u]+=size[v];
f[u]=max(f[u],size[v]);
}
f[u]=max(f[u],n-size[u]);
if(f[u]<f[center]||(f[u]==f[center]&&u<center)) center=u;
}
void bfs(){
q.push(center);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(dep[v]||v==center) continue;
dep[v]=dep[u]+1;
sum+=dep[v];
q.push(v);
}
}
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
center=0,f[0]=inf;
get(1,0);
bfs();
cout<<center<<' '<<sum;
return 0;
}
3.最近公共祖先（）:
概念：
什么是最近公共祖先？
每年过年走亲访友的时候，“认亲戚”是一个常见的话题。两个亲戚在聚会中碰面并开始聊天，不可避免的谈论辈分和称呼的话题。对他们而言，最简单的开始方法莫过于：“我爸跟你爸是兄弟”，“咱俩太爷爷是同一个人”等。
而最近公共祖先就是两个结点最接近的直系长辈。
如何求解任意两个结点的 :
（1）首先找到两个结点中较深的结点，设那个结点为 ，不停将 往上提，直到 的深度和 一样。
（2）同时将 和 一起往上提，直到它们一样为止。
是不是听起来，求解 很简单，接下来我们来看一道例题。
:
思路分析：
和刚才说的步骤一样，但是要先跑一遍 遍历每一个结点的深度。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int fa[N],d[N],n,m,rt;
vector<int>G[N];
void add(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int u){
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa[u]) continue;
fa[v]=u;
d[v]=d[u]+1;
dfs(v);
}
}
int lca(int u,int v){
if(d[u]<d[v]) swap(u,v);
while(d[u]!=d[v]) u=fa[u];
while(u!=v) u=fa[u],v=fa[v];
return u;
}
int main(){
cin>>n>>m>>rt;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
add(u,v);
}
dfs(rt);
for(int i=1;i<=m;i++){
int u,v;
cin>>u>>v;
cout<<lca(u,v)<<endl;
}
return 0;
}
但是你交上去会发现超时了，因为对于每一次询问，最坏的情况，就是遍历了整颗树，单次时间复杂度 ，显然会超时。
优化：
这里有两种常见的优化方法：倍增算法和 算法，在这里我只介绍倍增算法。
先观察一下我们之前的代码差在哪里，它每次往上提的速率太低了，有些不必要的结点花了许多时间。所以倍增算法就是将这段时间尽量压缩小一点，下面给出具体思路和方法。
现在将一个结点往上移动 的高度，可以考虑二进制分解，使得时间和空间上都令人满意。把 拆分成二进制数，然后如果第 位有 ，就向上提 层，这样时间复杂度就是 ，空间复杂度也就只有 完全可以接受。
（1）如何快速求出一个点的所有 级祖先？
继续按照套路来思考这个问题：每个结点所需要的信息是由父结点计算而来的，还是在回溯的时候由子结点的信息计算的呢？考虑计算的是某一个结点的祖先，那么肯定是要用它祖先结点的信息来计算。如何计算它的 级祖先呢？使用暴力算法显然不行，但是可以考虑到：+=。这就启发我们由 来推 。而本题中 的上限只有 ，所以方法可行。
（2）如何优化上提一个结点的过程？
由于可以发现本题里 的上限非常小，所以只用暴力枚举 就可以了。
完整代码如下：
#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int n,m,q,s;
int d[N],anc[N][20],dis[N];
vector<int>G[N];
inline void add(int u,int v){
G[u].push_back(v);
G[v].push_back(u);
}
inline void dfs(int u,int fa){
for(int i=0;i<G[u].size();i++){
int v=G[u][i];
if(v==fa) continue;
d[v]=d[u]+1;
anc[v][0]=u;
dfs(v,u);
}
}
inline void init(){
for(int j=1;j<=18;j++){
for(int i=1;i<=n;i++){
anc[i][j]=anc[anc[i][j-1]][j-1];
}
}
}
inline int lca(int u,int v){
if(d[u]<d[v]) swap(u,v);
for(int i=18;i>=0;i--){
if(d[anc[u][i]]>=d[v]) u=anc[u][i];
}
if(u==v) return u;
for(int i=18;i>=0;i--){
if(anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i];
}
return anc[u][0];
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr),cout.tie(nullptr);
cin>>n>>m>>s;
for(int i=1;i<n;i++){
int u,v; cin>>u>>v;
add(u,v);
}
d[s]=1,dfs(s,0);
init();
while(m--){
int u,v;
cin>>u>>v;
cout<<lca(u,v)<<endl;
}
return 0;
}
4.树的重链部分：
导言：
树的重链部分作为一种进一步划分树的结构的方式，具有良好的性质。它将树上的信息划分到链上，使得大部分处理序列问题的数据结构得以在树上应用，这里会来讲一下树的重链部分。
先给出一道题目，然后慢慢讲。
:
现在引入一个概念 序，什么是 序？假设维护一个序列，初始为空。从树的某个结点开始对树进行 ，每到达一个新的结点，就添加这个结点，最后会得到一个长度为 的序列，如图，从1开始的 序应为 。
根据结点编号的 序，可以得到对应点权照结点 序排列的序列 。尝试使用线段树维护这个序列。如果想把 1 到 6 号结点的路径上的点权都加上 ，注意到这条路上的结点 序上恰好是前四个，于是只需要对
全部评论 23
直径两次 dfs 只需要证明“一棵树上距离一个点最远的点一定是直径的两端之一”就行了吧，我这里有简要证明：https://www.acgo.cn/discuss/rest/53182
1周前 来自 广东
0
有帮助，赞一个