POJ 1655 求树的重心

时间：2022-07-16 18:50:03

POJ 1655

【题目链接】POJ 1655

【题目类型】求树的重心

&题意：

定义平衡数为去掉一个点其最大子树的结点个数，求给定树的最小平衡数和对应要删的点。其实就是求树的重心，找到一个点，其所有的子树中最大的子树的节点数最少，那么这个点就是这棵树的重心，删除重心后，剩余的子树更加平衡正好满足题意

&题解：

那么怎么求呢？我们可以求每个顶点的子树，把子树节点最多的赋为b，那么每个顶点都有一个b，最小的b就是树的重心，一颗树只有1个或2个重心。

【时间复杂度】\(O(n)\)

&代码：

#include <map>

#include <cmath>

#include <cstdio>

#include <vector>

#include <iostream>

#include <set>

#include <queue>

#include <cstring>

#include <algorithm>

using namespace std;

#define cle(a,v) memset(a,(v),sizeof(a))

#define fo(i,a,b) for(int i=(a);i<=(b);i++)

#define fd(i,a,b) for(int i=(a);i>=(b);i--)

#define ll long long

const int maxn = 2e4 + 7;

struct Edge {

	int v, next;

} edges[maxn * 2];

int tot, head[maxn];

void addedge(int u, int v) {

	edges[tot].v = v;

	edges[tot].next = head[u];

	head[u] = tot++;

}

int n, dp[maxn], an1, an2;

void dfs(int u, int fa) {

	int b = 0;

	for (int i = head[u]; ~i; i = edges[i].next) {

		int v = edges[i].v;

		if (v == fa)continue;

		dfs(v, u);

		dp[u] += dp[v] + 1;

		b = max(b, dp[v] + 1);

	}

	b = max(b, n - dp[u] - 1);

	if (an1 > b || an1 == b && an2 > u) {

		an1 = b;

		an2 = u;

	}

}

int main() {

	freopen("1.in", "r", stdin);

	int t;

	scanf("%d", &t);

	while (t--) {

		tot = 0;

		an1 = 1 << 30, an2 = 1 << 30;

		cle(head, -1); cle(dp, 0);

		scanf("%d", &n);

		for (int i = 0; i < n - 1; i++) {

			int u, v;

			scanf("%d%d", &u, &v);

			addedge(u, v);

			addedge(v, u);

		}

		dfs(1, -1);

		// fo(i, 1, n) {

		// 	printf("[%d]=%d ", i, dp[i]);

		// } printf("\n");

		printf("%d %d\n", an2, an1);

	}

	return 0;

}

相关文章