10926 - Level Order Traversal   

Description

給一棵tree,還有他的root,輸出這棵tree的level order traversal。

Note : 一個節點可能有大於兩個的孩子節點。

Note : 當一個節點有多個孩子需要造訪時,由數字編號小的節點開始造訪。

Input

第一行為一個正整數T(T<100),代表測資數,接下來每筆測資如下格式:

    第一行有2個整數,N R,分別代表N個點以及root為編號R的節點,所有點的編號為1~N。

     接下來有N-1行,每行有2個數字u v,代表編號u的節點與編號v的節點相連。

數字範圍:

0 < N <= 1000

Output

將所有測資最後一個輸出的節點編號加總後做輸出。

 

以sample testcase為例,這兩筆的level order traversal為:

1 2 3

5 2 3 4 1

因此我們的答案為3 + 1 = 4。

Sample Input  Download

Sample Output  Download

Tags

韩永楷老师数据结构mooc MOOC



Discuss