树的中心

一、定义

到树中其他结点的最远距离最近的结点为树的中心；

二、求法

求出向上最长路与向下最长路后，取两个值得最大值，即为到其他结点的最远距离；

找这个距离最近的点即可；

三、代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 10005
using namespace std;
int n, down1[MAXN], down2[MAXN], up[MAXN], ans = 2147483647;
bool flag[MAXN];
struct edge {
	int to, tot;
};
vector < edge > g[MAXN];
void dfs1(int i) {
	bool f = true;
	flag[i] = true;
	for (int t = 0; t < g[i].size(); t++) {
		int v = g[i][t].to, tot = g[i][t].tot;
		if (!flag[v]) {	
			dfs1(v);
			int ans = down1[v] + tot;
			if (f == true) {
				down1[i] = ans;
				down2[i] = -2147483647;
				f = false;
			} else {
				if (ans > down1[i]) {
					down2[i] = down1[i];
					down1[i] = ans;
				} else {
					down2[i] = max(down2[i], ans);
				}
			}
		
		}
	}
	flag[i] = false;
	return;
}
void dfs2(int i) {]
	flag[i] = true;
	int ans = 0;
	for (int t = 0; t < g[i].size(); t++) {
		int v = g[i][t].to, tot = g[i][t].tot;
		if (!flag[v]) {
			if (down1[i] == down1[v] + tot) {
				ans++;
			}
		}
	}
	for (int t = 0; t < g[i].size(); t++) {
		int v = g[i][t].to, tot = g[i][t].tot;
		if (!flag[v]) {
			up[v] = -2147483647;
			if (down1[i] != down1[v] + tot || (ans > 1 && down1[i] == down1[v] + tot)) {
				up[v] = max(up[v], max(up[i], down1[i]) + tot);
			} else {
				up[v] = max(up[v], max(up[i], down2[i]) + tot);
			}
			dfs2(v);
		}
	}
	return;
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++) {
		int x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		g[y].push_back( edge ( { x, z } ) );
		g[x].push_back( edge ( { y, z } ) );
	}
	dfs1(1);
	dfs2(1);
	for (int i = 1; i <= n; i++) {
		ans = min(ans, max(down1[i], up[i]));
	}
	printf("%d", ans);
	return 0;
}

最后

以上就是优美缘分最近收集整理的关于树的中心总结树的中心的全部内容，更多相关树内容请搜索靠谱客的其他文章。