Description

有一个棵树,树上有 n 个结点。结点的编号分别为 \(1 \ldots n\),其中 1 是树的根结点。现在希望你帮忙计算每个结点作为根结点的子树分别有多少结点。

  • 输入格式

第一行输入一个数字 n,代表树上结点的个数。\((2 \leq n \leq 1000)\)接下来的 n-1 行,每行俩个数字 a,b,代表结点 a 到结点 b 有一条边。

  • 输出格式

按编号顺序输出每个结点作为根结点的子树,分别有多少结点,中间用空格分开。

  • 样例输入
1
2
3
4
5
5
1 4
1 3
3 2
3 5
  • 样例输出
1
5 1 3 1 1

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1010;

struct Edge {
int v, next;
} e[maxn];

int p[maxn], id;
int n, cnt[maxn];
bool vis[maxn];

void init() {
memset(p, -1, sizeof(p));
memset(cnt, 0, sizeof(cnt));
memset(vis, false, sizeof(vis));
id = 0;
}

void insert(int u, int v) {
e[id].v = v;
e[id].next = p[u];
p[u] = id++;
}

void dfs(int u) {
vis[u] = true;
cnt[u] = 1;
for(int i = p[u]; i != -1; i = e[i].next) {
int v = e[i].v;
if(!vis[e[i].v]) {
dfs(e[i].v);
cnt[u] += cnt[e[i].v];
}
}
}

int main() {
init();
scanf("%d", &n);
for(int i = 1; i < n; ++i) {
int u, v;
scanf("%d %d", &u, &v);
insert(u, v);
insert(v, u);
}
dfs(1);
for(int i = 1; i <= n; ++i) {
printf("%d%c", cnt[i], " \n"[i == n]);
}
return 0;
}

Record

  • 2018年08月23日 完成题解