52 lines
1.3 KiB
C++
52 lines
1.3 KiB
C++
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
const int N = 2e5 + 10;
|
||
const int M = 4e5 + 10;
|
||
/*
|
||
3
|
||
1 3
|
||
2 3
|
||
|
||
答案 ：
|
||
2 2 1
|
||
*/
|
||
// 链式前向星
|
||
int e[M], h[N], idx, ne[M];
|
||
void add(int a, int b) {
|
||
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
|
||
}
|
||
int cnt[2]; // 两种颜色都有多少个
|
||
int color[N]; // 当前节点颜色,也可以理解为是奇偶性
|
||
/*
|
||
u 当前节点
|
||
c 当前节点颜色 【二分图染色，也可以理解为是奇偶性】
|
||
fa 当前节点的父节点
|
||
*/
|
||
void dfs(int u, int c, int fa) {
|
||
color[u] = c; // u节点标识为c这个颜色
|
||
cnt[c]++; // 颜色计数
|
||
for (int i = h[u]; ~i; i = ne[i])
|
||
if (e[i] != fa) // 不走回头路
|
||
dfs(e[i], c ^ 1, u); // 走向下一个节点，下一个节点的颜色需要变换,同时标识父节点是u
|
||
}
|
||
|
||
int main() {
|
||
// 初始化链式前向星
|
||
memset(h, -1, sizeof h);
|
||
int n;
|
||
cin >> n;
|
||
for (int i = 1; i < n; i++) {
|
||
int a, b;
|
||
cin >> a >> b;
|
||
add(a, b);
|
||
add(b, a);
|
||
}
|
||
|
||
// 深搜一次，从1号节点搜索，标识为0这个颜色，1的父节点不存在，传入0
|
||
dfs(1, 0, 0);
|
||
|
||
// 输出结果
|
||
for (int i = 1; i <= n; i++) // 每个节点都讨论一次，其实就是按颜色分两组，每组的个数输出即可
|
||
printf("%d ", cnt[color[i]]);
|
||
return 0;
|
||
} |