4680: 【GESP2503六级】树上漫步
内存限制：512 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：6
解决：1
题目描述
输入
第一行，一个正整数$n$ 。
接下来$n-1$ 行，每行两个整数$u_i,v_i$ ，表示树上有一条连接结点$u_i$ 和结点$v_i$ 的边。
接下来$n-1$ 行，每行两个整数$u_i,v_i$ ，表示树上有一条连接结点$u_i$ 和结点$v_i$ 的边。
输出
一行， $n$个整数，第$i$ 个整数表示从结点$i$ 出发开始漫步，能结束漫步的结点数量。
样例输入 复制
3
1 3
2 3样例输出 复制
2 2 1提示
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int cnt[N], bel[N];
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[ u ];
h[ u ] = et;
}
void dfs(int u, int c, int f) {
bel[ u ] = c;
cnt[c]++;
for (int i = h[ u ]; i; i = nx[i])
if (to[i] != f)
dfs(to[i], c ^ 1, u);
}
int main() {
scanf("%d", & n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", & u, & v);
ae(u, v);
ae(v, u);
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++)
printf("%d%c", cnt[bel[i]], " \n" [i == n]);
return 0;
}