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

# -*- coding:utf-8 -*-

if __name__ == '__main__':
    # n 树中节点个数
    # m 非叶子节点个数
    n, m = list(map(int, input().strip().split(' ')))
    # 二维数组
    # 元素的下标表示节点的 ID
    # 第 1 个元素不使用
    tree = [[] for _ in range(n+1)]
    while m != 0:
        tokens = list(map(int, input().split(' ')))
        _id = tokens[0]
        children = tokens[2:]
        tree[_id] = children
        m = m - 1

    # 记录每一层叶子节点的数量
    counts = [0 for _ in range(n+1)]
    # 记录最大深度
    max_depth = 0

    def dfs(i, depth):
        global max_depth, counts, tree

        if len(tree[i]) == 0:  # 节点 i 为叶子节点
            counts[depth] = counts[depth] + 1
            max_depth = max(depth, max_depth)
            return
        for j in tree[i]:
            dfs(j, depth + 1)

    dfs(1, 0)

    print(' '.join([str(count) for count in counts[:max_depth+1]]))