吐槽不给数据范围,垃圾题目
题目连接:[保卫村庄 (nowcoder.com)](https://ac.nowcoder.com/acm/problem/214212)
x
using namespace std;
const int N = 1e5 + 10;
const int M = N << 1;
//dis[u]: 表示以u为根的总距离
int n;
int to[M], head[N], ne[M], cnt; // 链式前向星
// 加无向边
void add_edge(int a, int b) {
to[++cnt] = b;
ne[cnt] = head[a];
head[a] = cnt;
}
int size[N]; // size[i] = 统计以每个节点i为根节点的树的节点数量
bool vis[N]; // 标记数组
int ct = -1;
int ans = N; // 记录最大子树节点数量最小值
inline int dfs(int u) { // 计算以u为根的树的节点个数
size[u] = 1; // 自己本身就是一颗树
int res = 0; // 记录最大子树节点数量
vis[u] = true;
for (int i = head[u]; i; i = ne[i]) {
if (vis[to[i]]) continue;
size[to[i]] = dfs(to[i]); //计算以to[i]为根的树的节点个数
res = max(res, size[to[i]]); // 记录最大子树节点数量
size[u] += size[to[i]];
}
res = max(res, n - size[u]); // 记录最大子树节点数量
// ans = min(ans, res);
if (ans > res) { // 记录最大子树节点数量最小值
ans = res;
ct = u;
}
if (res == ans && u < ct) ct = u;
return size[u];
}
int main() {
scanf("%d", &n); //输入节点个数
for (int i = 1; i <= n - 1; i++) { //输入n - 1条边
int a, b; //输入边的两端
scanf("%d %d", &a, &b);
add_edge(b, a), add_edge(a, b);
}
dfs(1); // 以1为根节点进行搜索
for (int i = 1; i <= n ;i++) printf("size[%d] = %d\n", i, size[i]);
printf("%d %d\n", ct, ans + 1);
return 0;
}