Home => ProblemSet => 7.1-12:树的大小与深度
Problem1740--7.1-12:树的大小与深度

1740: 7.1-12:树的大小与深度

Time Limit: 1 Sec  Memory Limit: 128 MB  Submit: 0  Solved: 1
[ Submit ] [ Status ] [ Creator: ][ 参考程序 ]

Description

求树中每棵子树的大小以及每个结点的深度(假设结点1为根)

Input

第一行一个整数n，表示树的结点个数
接下来 n - 1 行，每行两个整数 x 和 y，表示结点 x 和结点 y 之间有一条边，但不保证 x 是 y 的父结点

Output

共n行，第 i 行为两个正整数，分别表示以结点 i 为根的子树大小和该结点 i 的深度

Sample Input Copy 

4
1 4
1 3
2 4

Sample Output Copy 

4 1
1 3
1 2
2 2

HINT

每个点的子树大小为它的所有子结点的子树大小之和再加 1。每个点的深度为它父结点的深度加 1。

0 < n <= 1000

Source/Category

数据结构 树 
[ Submit ] [ Status ]