SGU 134.Centroid(图心)

时间:2023-02-01 06:31:56

SGU链接

时间限制:0.25s

空间限制:4M

题意

给出一个树(节点数<=16000),一个节点的重量定义为从树中去除这个点后,新得到的所有树中节点最多的树的节点数。树的中心定义为所有节点重量最小的那几个。

要求输出给定树的树的中心的重量,以及所有的树心的编号。


Solution

首先,以任意节点为根,构造一颗具有父子节点关系的树。

使用递归即可,Fa[i]记录i的父亲节点编号。

sum[i],记录i节点以其所有儿子节点一共有多少个节点。

显然如果以1号节点为根 sum[1]=n;

再来考虑如何得到一个节点的重量。

对于根节点,它的重量是 所有 儿子节点sum[j]中的最大值。

对于根节点的儿子k呢?

它的重量是他的 所有儿子节点的sum[]和 (sum[1]-sum[k])的最大值。

那么对于k的儿子呢?

这时可以注意到计算k 的时候与根节点其他儿子已经没有关系了,需要的只是sum[i],

在计算k儿子时,把k当做根,这时sum[k]=n;

设p为k的儿子,

p的重量就是 它所有儿子的sum[]和 (sum[k]-sum[p])的最大值.

最后只要存下不同重量的节点有哪一些输出就可以了。

参考代码:

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#define INF 16666
using namespace std;
struct node {
int v, ne;
} edge[INF<<2];
queue<int> ql;
int head[INF], fa[INF], pd[INF];
int sum[INF], cnt, nCnt[INF];
vector<int> out[INF];
int n, m, ans = INF;
void added (int u, int v) {
edge[++cnt].v = v;
edge[cnt].ne = head[u];head[u] = cnt;
}
int Count (int x) {
pd[x] = sum[x] = 1;
for (int i = head[x]; i != 0; i = edge[i].ne) {
int j = edge[i].v;
if (!pd[j]) {
fa[j] = x;
sum[x] += Count (j);
}
}
return sum[x];
}
void make (int x) {
int k=0;
if (fa[x] != 0) k = sum[fa[x]] - sum[x];
for (int i = head[x]; i != 0; i = edge[i].ne) {
int j = edge[i].v;
if (j != fa[x]){
k = max (k, sum[j]);
if(fa[x]!=0) sum[x]=sum[fa[x]];
make(j);
}
}
if (ans >= k) {
ans = k;
out[k].push_back (x);
nCnt[k]++;
}
}
int main() {
int x, y, c;
scanf ("%d", &n);
for (int i = 1; i <= n - 1; i++) {
scanf ("%d %d", &x, &y);
added (x, y), added (y, x);
}
Count (1);
make (1);
printf ("%d %d\n", ans, nCnt[ans]);
sort (out[ans].begin(), out[ans].end() );
for (int i = 0; i <= out[ans].size() - 1; i++)
printf ("%d ", out[ans][i]);
return 0;
}