树的重心cpp

#include 
#include 
#include 

using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

const int N = 100010, M = N * 2;
int n;
int h[N];  // 邻接表 存储 n个节点 所以需要n个队列头结点
int e[M];  // 存储元素
int ne[M];  // 存储列表的next值
int idx;  // 单链表指针

bool st[N];  
int ans = N;  // 表示重心的所有的子树中，最大的子树的结点数

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


// 以u为根的子树的大小
 
int dfs(int u) {
    int res = 0; //存储 删掉某个节点之后，最大的连通子图节点数
    st[u] = true; //标记访问过u节点
    int sum = 1; //存储 以u为根的树 的节点数, 包括u，如图中的4号节点

    //访问u的每个子节点
    for (int i = h[u]; i != -1; i = ne[i]) {
        int j = e[i];
        //因为每个节点的编号都是不一样的，所以 用编号为下标 来标记是否被访问过
        if (!st[j]) {
            int s = dfs(j);  // u节点的单棵子树节点数 如图中的size值
            res = max(res, s); // 记录最大联通子图的节点数
            sum += s; //以j为根的树 的节点数
        }
    }

    //n-sum 如图中的n-size值，不包括根节点4；
    res = max(res, n - sum); // 选择u节点为重心，最大的 连通子图节点数
    ans = min(res, ans); //遍历过的假设重心中，最小的最大联通子图的 节点数
    return sum;
}
 
int main()
{
    IOS;
    cin >> n ;
        
    memset(h, -1, sizeof h);
    for (int i = 0; i < n - 1; i ++)
    {
        int a, b;
        cin >> a >> b;
        add(a,b), add(b,a);
    }

    
    dfs(1);
    
    cout << ans << endl;
    
    return 0;
}