A28364. 树上漫步
填空题
困难
知识点
题目描述
树上漫步
题目描述
小 A 有一棵n个结点的树，这些结点依次以1，2，...，n 标号。
小 A 想在这棵树上漫步。具体来说，小 A 会从树上的某个结点出发，每一步可以移动到与当前结点相邻的结点，并且小 A 只会在偶数步（可以是零步）后结束漫步。
现在小 A 想知道，对于树上的每个结点，从这个结点出发开始漫步，经过偶数步能结束漫步的结点有多少个（可以经过重复的节点）。
输入格式
第一行，一个正整数n 。
接下来n-1行，每行两个整数ui，vi ，表示树上有一条连接结点ui 和结点vi 的边。
输出格式
一行， n个整数，第 i个整数表示从结点i出发开始漫步，能结束漫步的结点数量。
样例
输入样例 1
3
1 3
2 3输出样例 1
2 2 1输入样例 2
4
1 3
3 2
4 3输出样例 2
3 3 1 3 数据范围
对于 40% 的测试点，保证1≤n≤103 。
对于所有测试点，保证 1≤n≤2×105。
参考答案
#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;
}
上一题
下一题