原题链接

解题思路

1. 题目给出树的边都是无向边，所以该树可以被看成是图。

2. 为什么输出最大值的最小值？

   • 因为可能不止一个重心

3. 存储方式：

   • a. 邻接矩阵（适合存储稠密图）
   • b. 邻接表（拉链法(本题存法)）

4. 全局变量ans的作用(记录最小的最大值)

5. 一般来说题目只需要遍历一次，需要有一个bool数组st[N]记录哪些点已经被遍历过了。

6. 使用头插法构建邻接表（e[idx] = b; ne[idx] = h[a]; h[a] = idx++;）

7. // 树&图的深度优先搜索代码
   void dfs(int u)
   {
   	st[u] = true; // 标记一下，已经被搜过了
   
   	// 遍历节点u的每一个出边
   	for(int i = h[u]; i != -1; i = ne[i])
   	{
   		// 存储该节点对应图中的位置
   		int j = e[i];
           // 如果该节点尚未被dfs访问过,则进行递归
   		if(!st[j]) dfs(j);
   	}
   }
   

8. 根据这道题的要求，dfs()需要做的对应的操作

   • dfs()函数返回以u为根的节点个数 sum += s;
   • 去除重心后连通块的最大值，max(n - sum, res)
   • 全局变量ans---最大值的最小值，min(ans, sum)

// 以u为根的子树中点的数量
int dfs(int u)
{
    st[u] = true; // 标记一下，已经被搜过了
    
    // "sum":以u为根的子树的节点总个数，"res":将u删掉后每一个连通块大小的最大值	
    int sum = 1; res = 0;
    
    for(int i = h[u]; i != -1; i = ne[i])
    {
        // 存储当前节点对应图的位置
        int j = e[i];
        // 如果该节点尚未被dfs访问过,则进行递归
        if (!st[j])
        {
            int s = dfs(j);		// return sum 返回的值
            res = max(res, s);
            sum += s;
        }
    }
    res = max(res, n - sum);
    
    ans = min(ans, res);
    
    return sum;
}

参考代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
// 无向图两节点之间有两条边
const int M = N * 2;

int h[N], e[M], ne[M], idx, n;
// 全局变量，用于记录去掉重心后的子树节点个数所有最大值的最小值
int ans = N;
// 记录该节点是否在dfs的过程中被遍历过
bool st[N];


void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
    
}

int dfs(int u)
{
    st[u] = 1;
    // 以u为根的子树的节点个数, res：除去u的连接块的节点个数的最大值
    int sum = 1, res = 0;
    for(int i = h[u]; i!= -1; i = ne[i])
    {
        int j = e[i];
        if(!st[j]) 
        {
            int s = dfs(j);
            res = max(res, s);
            sum += s;
        }
    }
        
    res = max(res, n - sum);
    ans = min(res, ans);
    
    return sum;
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    
    int a, b;
    for(int i = 0; i < n - 1; i ++)
    {
        cin >> a >> b;
        add(a, b), add(b, a);
    }
    
    dfs(1);
    
    cout << ans << endl;
    return 0;
}