1 条题解

  • 0
    @ 2026-2-17 21:58:25
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] 全局常量与变量定义
    const int MAXN = 1e5 + 10; // 适配题目n≤1e5的规模
    vector<int> g[MAXN];        // 邻接表,存储树的无向边
    int n;                       // 树的总结点数
    int sz[MAXN];                // sz[u]:以u为根的子树的总结点数
    int min_max_block = INT_MAX; // 记录所有结点中,删除后的最大连通块的最小值
    vector<int> center;          // 存储树的重心结点
    
    // [2] DFS核心函数:计算子树大小,同时求解重心
    // 参数说明:u=当前遍历的结点,fa=当前结点的父结点(避免往回走)
    void dfs(int u, int fa)
    {
        sz[u] = 1; // 子树初始大小为当前结点自身
        int max_block = 0; // 记录删除当前结点u后,最大的连通块大小
    
        // 遍历当前结点的所有邻接结点
        for(int v : g[u])
        {
            if(v == fa) continue; // 跳过父结点,防止死循环
            dfs(v, u);            // 递归计算子结点的子树大小
            sz[u] += sz[v];       // 累加子树大小到当前结点
            max_block = max(max_block, sz[v]); // 更新子树中的最大连通块
        }
    
        // 加上父节点方向的连通块大小,得到删除u后的最大连通块
        max_block = max(max_block, n - sz[u]);
    
        // [3] 更新重心:如果当前结点的最大连通块更小
        if(max_block < min_max_block)
        {
            min_max_block = max_block;
            center.clear();       // 清空之前的重心
            center.push_back(u);  // 加入当前结点为新的重心
        }
        // 如果和当前最小值相等,说明有多个重心,加入列表
        else if(max_block == min_max_block)
        {
            center.push_back(u);
        }
    }
    
    int main()
    {
        // 关闭cin同步,加速输入,避免n=1e5时输入超时
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    
        // [4] 输入总结点数
        cin >> n;
        // [5] 输入n-1条无向边,构建邻接表
        for(int i = 1; i <= n-1; i++)
        {
            int x, y;
            cin >> x >> y;
            g[x].push_back(y);
            g[y].push_back(x); // 无向边双向存储
        }
    
        // [6] 从结点1开始DFS,根节点的父结点设为-1(不存在的结点)
        dfs(1, -1);
    
        // [7] 按题目要求,将重心从小到大排序
        sort(center.begin(), center.end());
    
        // [8] 输出结果
        for(int i = 0; i < center.size(); i++)
        {
            if(i > 0) cout << " ";
            cout << center[i];
        }
        cout << endl;
    
        return 0;
    }
    
    • 1

    信息

    ID
    1083
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者