G6013 [GESP202503 六级] 树上漫步 题解

知识点：树、二分图、奇偶性。

解题思路

将树二染色，统计两种颜色的节点数。每个节点的答案是与它同色的节点数量。

为什么正确

每走一条边颜色翻转，偶数步后只能到同色点；树中同色点间唯一路径长度为偶数，均可到达。

易错点

允许零步，因此起点本身也要计入；不必为每个起点重复搜索。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<vector<int>>g(n+1);
    for(int i=1;i<n;i++) {
        int u,v;
        cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<int>col(n+1,-1),q= {
        1
    }
    ;
    col[1]=0;
    long long ct[2]= {
        1,0
    }
    ;
    for(int i=0;i<(int)q.size();i++) {
        int u=q[i];
        for(int v:g[u])if(col[v]<0) {
            col[v]=col[u]^1;
            ct[col[v]]++;
            q.push_back(v);
        }
    }
    for(int i=1;i<=n;i++)cout<<ct[col[i]]<<" ";
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用10个自行生成的测试点。