【树】树的直径和重心

目录

一.树的直径

（1）定义

（2）思路

（3）例题 

（4）std(第一小问)

二.树的重心

（1）介绍

（2）求重心

（3）例题

（4）AC

---

一.树的直径

（1）定义

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

（2）思路

（3）例题 

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

（4）std(第一小问)

#include
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
		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
#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];
		root=u;
	} 
}
 
int main(){
	scanf("%d",&n);
	int x,y;
	for(int i=1;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
#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];
		root=u;
	} 
}
struct node{
	int u,w;
	bool operator < (const node &x) const{
		return x.w
	}
};
int dis[maxn],vis[maxn];
void Djkstra(){
	for(int i=1;i<=n;i++) dis[i]=0x7fffffff;
	dis[root]=0;
	priority_queue 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[u]+w;
				q.push((node){v,dis[v]});
			}
		}
	}
}
int main(){
	scanf("%d",&n);
	int x,y;
	for(int i=1;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;
}