【树】树的直径和重心

目录

一.树的直径

（1）定义

（2）思路

（3）例题 

（4）std(第一小问)

二.树的重心

（1）介绍

（2）求重心

（3）例题

（4）AC

---

一.树的直径

（1）定义

树的直径是指树中最长的一条路径的长度，这条路径连接树中的两个节点，使得它们之间的距离最远。

（2）思路

（3）例题 

P3304 [SDOI2013] 直径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（4）std(第一小问)

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n;
struct Edge{int u,v,w,next;
}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int root,lon;
void dfs(int u,int fa,int p){if(p>lon){root=u;lon=p;}for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v==fa) continue;dfs(v,u,p+edge[i].w);}
}
int main(){scanf("%d",&n);for(int i=1,u,v,w;i<n;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w); add(v,u,w);}dfs(1,0,0);lon=0;dfs(root,0,0);printf("%d",lon);return 0;
}

---

二.树的重心

（1）介绍

 树的重心是指树中的一个节点，通过删除该节点后，将树分成多个子树，使得每个子树的节点数都不超过整棵树节点数的一半。换句话说，树的重心是树的一种结构特征，它能够将树尽可能平衡地分割成多个相对均匀的部分。

说人话就是重心在树所有节点中，它的最大子树的节点最小

寻找树的重心通常可以通过以下步骤来实现：

1. 选择任意一个节点作为树的根节点。
2. 对树进行深度优先搜索（DFS）或广度优先搜索（BFS），计算每个节点的子树大小（包括自身节点）。
3. 对于每个节点，计算删除该节点后，各个子树的大小（即除去该节点后，以其邻居节点为根的子树大小）。
4. 找到一个节点，使得删除该节点后，各个子树的大小都不超过整棵树节点数的一半。这个节点就是树的重心。

（2）求重心

#include<bits/stdc++.h>
#define maxn 10005
using namespace std;
int n;
int size[maxn],f[maxn]; //子树总大小 && 最大子树 
struct Edge{int u,v,next;
}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v){edge[++cnt]=(Edge){u,v,head[u]}; head[u]=cnt;
}
int root,MAX=0x7fffffff;
void dfs(int u,int fa){size[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs(v,u);size[u]+=size[v];f[u]=max(f[u],size[v]);}}f[u]=max(f[u],n-size[u]);if(f[u]<MAX ||f[u]<=MAX && u<root){MAX=f[u];root=u;} 
}int main(){scanf("%d",&n);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y); add(y,x);}dfs(1,0);printf("%d",root);return 0;
}

（3）例题

P1395 会议 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

（4）AC

#include<bits/stdc++.h>
#define maxn 50005
using namespace std;
int n;
int size[maxn],f[maxn]; //子树总大小 && 最大子树 
struct Edge{int u,v,w,next;
}edge[maxn<<1];
int head[maxn],cnt;
void add(int u,int v,int w){edge[++cnt]=(Edge){u,v,w,head[u]}; head[u]=cnt;
}
int root,MAX=0x7fffffff;
void dfs(int u,int fa){size[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v;if(v!=fa){dfs(v,u);size[u]+=size[v];f[u]=max(f[u],size[v]);}}f[u]=max(f[u],n-size[u]);if(f[u]<MAX ||f[u]<=MAX && u<root){MAX=f[u];root=u;} 
}
struct node{int u,w;bool operator < (const node &x) const{return x.w<w;}
};
int dis[maxn],vis[maxn];
void Djkstra(){for(int i=1;i<=n;i++) dis[i]=0x7fffffff;dis[root]=0;priority_queue<node> q;q.push((node){root,0});while(!q.empty()){node temp=q.top(); q.pop();int u=temp.u;if(vis[u]) continue;vis[u]=1;for(int i=head[u];i;i=edge[i].next){int v=edge[i].v,w=edge[i].w;if(dis[u]+w<dis[v]){dis[v]=dis[u]+w;q.push((node){v,dis[v]});}}}
}
int main(){scanf("%d",&n);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add(x,y,1); add(y,x,1);}dfs(1,0);printf("%d ",root);Djkstra();long long ans=0;for(int i=1;i<=n;i++) ans+=dis[i];printf("%lld",ans);return 0;
}