1 条题解

  • 0
    @ 2025-12-2 15:58:58
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=2e5+5;
    vector <int> a[maxn]; //邻接表,记录点与边的关系
    int deep[maxn]; //记录每个节点的深度
    int cnt[maxn]; //统计树每层的节点数量
    int maxDeep=1,c1=0,c2=0;//树的最大深度,奇数层节点总数,偶数层节点总数
    int n;
    
    void dfs(int v, int f){
        deep[v]=deep[f]+1; //记录当前节点在第几层
        maxDeep=max(maxDeep,deep[v]); //计算树的最大深度
        cnt[deep[v]]++; //当前节点所在层的节点总数+1
        //遍历当前节点的邻居
        for(int i=0;i<int(a[v].size());i++){
            int nv=a[v][i]; //邻居
            if(nv==f) continue; //避免无限递归
            dfs(nv,v);
        }
    }
    
    int main(){
        int u,v;
        cin >> n;
        //用邻接表记录所有节点之间的邻接关系
        for(int i=1;i<n;i++){
            cin >> u >> v;
            a[u].push_back(v);
            a[v].push_back(u);
        }
        //深搜遍历整棵树,记录每个节点所在层,以及统计树的每层的节点总数
        dfs(1,0);
        //
        for(int i=1;i<=maxDeep;i++){
            if(i&1) c1+=cnt[i]; //奇数层节点数量
            else c2+=cnt[i]; //偶数层节点数量
        }
        //
        for(int i=1;i<=n;i++){
            if(deep[i]&1) cout << c1 << " ";
            else cout << c2 << " ";
        }
        //
        return 0;
    }
    
    • 1

    树上漫步(洛谷 P11962 普及-)(邻接表+DFS)t10

    信息

    ID
    1229
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    (无)
    递交数
    7
    已通过
    2
    上传者