树的综合统计

题目描述

给定一棵包含 n 个节点的无向树，节点编号为 1 到 n。规定节点 1 为根节点，根节点深度为 1。

请计算：

1. 叶子节点的数量；
2. 整棵树的高度，即所有节点深度的最大值；
3. 每个节点的子树大小 siz[i]，即节点 i 与它的全部后代的数量。

叶子节点指在以 1 为根后，没有子节点的节点。特别地，当 n=1 时，节点 1 也是叶子节点。

输入格式

第一行一个整数 n。

接下来 n-1 行，每行两个整数 u、v，表示节点 u 和节点 v 之间有一条无向边。

输出格式

第一行输出两个整数：叶子节点数量和树的高度。

第二行输出 n 个整数，第 i 个整数表示 siz[i]。

8
1 2
1 3
2 4
2 5
5 8
3 6
3 7

4 4
8 4 3 1 2 1 1 1

数据范围

• 1 <= n <= 100000
• 输入保证给出的是一棵树