牛客保卫村庄之树的重心

吐槽不给数据范围，垃圾题目

题目连接：保卫村庄 (nowcoder.com)

#include <stdio.h>

using namespace std;

#define max(a, b) ({\
    (a) > (b) ? (a) : (b);\
})

#define min(a, b) ({\
    (a) < (b) ? (a) : (b);\
})

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;
}