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

在一棵树上移动

1

步，一定会使深度改变

1

，所以移动

2

步，深度的改变为

0

或

2

，所以移动偶数步，深度改变量一定是偶数。

那么可以将深度为奇数的点分为一类，深度为偶数的点分为一类，此时每一类中的点是可以用偶数步互相到达的，而不同类的点无法通过偶数步到达，所以只要统计深度为奇数的点的个数

sum

，那么所有深度为奇数的点输出

sum

，否则输出

n-sum

。时间复杂度为

\mathcal{O}(n)

。

CPP

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

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

文章操作

相关推荐

评论

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