http://blog.csdn.net/xkzju2010/article/details/46868273

A family hierarchy is usually PResented by a pedigree tree. Your job is to count those family members who have no child.

Input

Each input file contains one test case. Each case starts with a line containing 0 < N < 100, the number of nodes in a tree, and M (< N), the number of non-leaf nodes. Then M lines follow, each in the format:

ID K ID[1] ID[2] … ID[K]

where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01.

Output

For each test case, you are supposed to count those family members who have no child for every seniority level starting from the root. The numbers must be printed in a line, separated by a space, and there must be no extra space at the end of each line.

The sample case represents a tree with only 2 nodes, where 01 is the root and 02 is its only child. Hence on the root 01 level, there is 0 leaf node; and on the next level, there is 1 leaf node. Then we should output “0 1” in a line. Sample Input

2 1 01 1 02

Sample Output

0 1 1082/5000

Sample Input 2 1 01 1 02 Sample Output 0 1

又如：

重新遍歷計算層數解析：孩子的level一定是父親的level+1，這個是顯然的。03 1 07 02 3 04 05 06 01 2 02 03 我第一行輸入的是3號結點，第二行輸入的2號結點，第三行輸入的是根結點，根據這個輸入順序就不好判斷3到底是第幾層了。

隊列解析：剛開始，跟結點入隊，就是1入隊。然后進入while，判斷隊列是不是空，發現不是空，進入循環體，然后隊列元素出隊，返回u 這個u是樹里邊結點的編號，u現在是1，就是根結點。curlev是當前這個結點(根結點)的層號，tree[u].lev是u號節點的層號，curlev和lev都是0，然后跳過if，執行下面的東西。if(tree[u].k==0)是判斷當前這個節點的孩子數量是不是0，如果是0就當然是葉子節點了。這里因為根節點有兩個孩子2和3，所以不是葉子節點，然后底下那個for循環是依次讓當前節點的孩子入隊，就是把根結點的所有孩子依次入隊，現在隊列里是2和3。這樣第一遍循環就完了，再從頭開始。現在隊列的元素是2和3，隊列不為空，執行下面的循環體。u=q.front()得到隊頭元素，u=2，是第02號結點。然后curlev=1，是02結點的層數，這里if判斷curlev和lev不相等,不相等了，說明遍歷到下一層了，這時候就執行if底下的代碼，輸出cnt，就是上一層的葉子結點數量，是0,然后讓cnt=0，重新統計現在這層的葉子結點，并讓lev=curlev，更新lev，代表遍歷到這層了。再下面的if是判斷u這個結點是不是葉子結點，02號有3個孩子，不是葉子結點，cnt不++。然后下面的for是把02號的3個孩子依次入隊?，F在隊列的元素是3 4 5 6。第三次進入while循環，不為空，q.front()得到隊頭，是3號結點，并出隊。判斷curlev和lev是不是相等的，此時兩個都是1，相等跳過if。判斷3是不是葉子結點，因為3有一個孩子不是葉子結點，然后把3號結點的所有孩子入隊，就是把7入隊。此時隊列元素是4 5 6 7。然后循環再開始，隊列不空，繼續得到隊頭元素是4號結點，q.pop()出隊，curlev這時候是04號結點的層數，是2，而lev是1，此時兩個不等，不相等就要打印結果了cnt=0，打印0，并把step更新，step=2了，然后判斷04號是不是葉子結點，發現04號的k是0，說明他是葉子結點，cnt++，因為k是0，所以下面的for就不執行了，現在隊列的元素是5 6 7，然后這三個元素的執行過程和4號結點是一樣的，略。最后隊列是空了，退出while循環，底下有一句打印cnt，就是把最后一層的葉子結點數量打印出來。