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

lly66666 · 2025-03-23 16:00:37 · 题解

非常简单的深搜题。

我们用两个数组：num 和 vis 来分别存储偶数点和奇数点的个数和每个点的奇偶情况，并在深搜的时候统计就行了。

代码：

#include <bits/stdc++.h>
using namespace std;
int num[1000005], vis[1000005], n, u, v;
vector<int> g[1000005];
void dfs(int x, int walk) {
    if(walk % 2 == 0) {
        num[2] ++;
        vis[x] = 2;
    }
    else {
        num[1] ++;
        vis[x] = 1;
    }
    for(int i = 0; i < g[x].size(); i ++) {
        if(!vis[g[x][i]]) dfs(g[x][i], walk + 1);
    }
}
int main() {
    cin >> n;
    for(int i = 1; i <= n; i ++) {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for(int i = 1; i <= n; i ++) {
        cout << num[vis[i]] << ' ';
    }
    return 0;
}

完结撒花！

管理员大大大大大大大大大大大大大大求过。