自动搬运

查看原文

来自洛谷，原作者为

	lly66666 **

搬运于2025-08-24 23:11:42，当前版本为作者最后更新于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;
}

完结撒花！

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