树的重心

图的存储

稠密图采用稀疏矩阵，稀疏图邻接表

树是无欢连通图，所以按照图的方式存储就行

这里邻接表采用第二章数组模拟链表的方式来写，当然也可以用$vector$来存储，只是效率稍微低了一点

思路分析

这里的树是无向图，每次建图都要添加两条边

树的dfs

因为树是联通的，所以从任何一个点开始都可以向下遍历。平时学的树是有向的，也就是要求必须从上向下遍历。这里是无向图，所以当前结点遍历后就要打上标记，防止树从下往上遍历而陷入死循环

求连通块大小

首先，我们删除当前结点后会剩下子树和该节点上面的连通块，我们让每次$dfs$某结点时返回当前子树的大小。每次遍历到某个点，我们就可以求出所有子树的最大值，这时用总数-子树节点数-1（当前结点）可以得到上方连通块个数，再进行比较

答案ans置于全局变量，每遍历一个结点更新一次

关于递归

本题一个基本的想法是将返回子树大小的写一个函数，然后我们对每一个结点都深搜一次，利用上面计算思路得到局部解，然后综合求值

y总是把两步合并写的，递归到叶子结点时候，它依次由下向上的计算，每次计算都会更新结点，从而得到正确答案

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = N * 2; // 边最多是点的两倍

int n;
int h[N], e[M], ne[M], idx;
int ans = N; // 初始给ans赋一个大值，以后去min才能取下去，很明显ans最大也就是N - 1
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] = true; // 当前结点已被遍历

    int size = 0, sum = 0; // size表示连通块的最大值， sum表示子树结点之和
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i]; // 取出子树结点编号
        if (st[j]) continue; // 防止向上遍历

        int s = dfs(j); // 搜索子节点
        size = max(size, s);
        sum += s;
    }

    size = max(size, n - sum - 1); // 连通块最大值是子树最大值与上面最大值中最大的数
    ans = min(ans, size); // ans要的是最大值得最小值

    return sum + 1; // 当前子树结点和是当前结点 + 该结点子树和
}

int main()
{
    scanf("%d", &n);

    memset(h, -1, sizeof h); // 链表头结点记得初始化

    for (int i = 0; i < n - 1; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b), add(b, a); // 树是无环连通图
    }

    dfs(1); // 搜索任意一个点都可以

    printf("%d\n", ans);

    return 0;
}