4680: 【GESP2503六级】树上漫步
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：2
解决：1
题目描述
一棵$n$ 个结点的树，这些结点依次以$1,2,...,n$ 标号。
小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。
现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。
小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。
现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。
输入
第一行，一个正整数$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;
}