题解：P11962 [GESP202503 六级] 树上漫步

L0_0 · 2025-03-23 21:36:57 · 题解

在一棵树上移动 1 步，一定会使深度改变 1，所以移动 2 步，深度的改变为 0 或 2，所以移动偶数步，深度改变量一定是偶数。

那么可以将深度为奇数的点分为一类，深度为偶数的点分为一类，此时每一类中的点是可以用偶数步互相到达的，而不同类的点无法通过偶数步到达，所以只要统计深度为奇数的点的个数 sum，那么所有深度为奇数的点输出 sum，否则输出 n-sum。时间复杂度为 \mathcal{O}(n)。

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+1;
int n, u, v, dep[N], sum;
bool vis[N];
vector<int> e[N];
void dfs(int u){
    vis[u] = 1;
    if (dep[u] % 2) sum++;
    for(auto v:e[u]){
        if (vis[v]) continue;
        dep[v] = dep[u] + 1;
        dfs(v);
    }
    vis[u] = 0;
}

int main(){
    cin>>n;
    for(int i=1;i<n;i++){
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        if (dep[i] % 2) cout << sum;
        else cout << n-sum;
        cout << ' ';
    }
}