d459: 一棵小樹
Tags : DP
Accepted rate : 130人/136人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-13 01:12

Content

  現在給你一張圖,之後將節點 1 往上拉,將此圖形變成一棵樹 ( tree )

請求出每一節點以下所有點的個數。

範例輸入1 :

 

 

節點 1 以下有 8 個節點( 有節點1 2 3 4 5 6 7 8 )
節點 4 以下有 3 個節點( 有節點4 5 6 )

... 類推


※ 你可能需要判斷誰是子節點,誰是父節點
※ 在測資中能保證 , 畫成圖之後 , 由節點 1 拉起必定是一棵樹
※ 每一個點連接的點不超過 300 個
※ 節點 1 是最上層的節點

Input
輸入內容的第一行只有一個數字 n,代表輸入樹狀圖的頂點數。
後面會接 n-1 行數字,每一行有兩個數字以空白隔開
代表該圖一個邊的兩個頂點,頂點的編號從 1 到 n。測詴資料中 n 的可能最大值為 20000.
Output

對 1~n 個點,輸出他下面有幾個節點。一個數字為節點編號(不足5位補空格)

中間有一個減號,後面的數字為該點以下的節點個數(不足5位補空格)(涵蓋該點)。

Sample Input
範例輸入 1:  //此行不會出現在測資中
8        
1 2
1 3
3 4
3 7
3 8
4 6
4 5
範例輸入 2://此行不會出現在測資中
10
1 5
1 10
5 2
3 5
10 7
6 10
4 7
9 7
3 8
Sample Output
範例輸出 1://此行不會出現在測資中
    1-    8
    2-    1
    3-    6
    4-    3
    5-    1
    6-    1
    7-    1
    8-    1
範例輸出 2://此行不會出現在測資中
    1-   10
    2-    1
    3-    2
    4-    1
    5-    4
    6-    1
    7-    3
    8-    1
    9-    1
   10-    5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (10%): 1.0s , <1K
公開 測資點#1 (10%): 1.0s , <1K
公開 測資點#2 (10%): 1.0s , <1M
公開 測資點#3 (10%): 1.0s , <1M
公開 測資點#4 (10%): 1.0s , <1M
公開 測資點#5 (10%): 1.0s , <1M
公開 測資點#6 (10%): 1.0s , <1M
公開 測資點#7 (10%): 1.0s , <1M
公開 測資點#8 (10%): 1.0s , <1K
公開 測資點#9 (10%): 1.0s , <1K
Hint :

DP

Tags:
DP
出處:
[管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」