回分類題庫
g077: F.一棵開花的樹
關鍵字: NPSC 2010 國中組決賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 24 Times / 24 Users | Submit : 62 Times / 28 Users | Accepted rate : 86%
題目加入時間 : 2012-01-13 16:38

Content: 简体中文

如何讓你遇見我
在我最美麗的時刻為這
我已在佛前求了五百年
求祂讓我們結一段塵緣
佛於是把我化做一棵樹
長在你必經的路旁
陽光下慎重地開滿了花
朵朵都是我前世的盼望
當你走近請你細聽
那顫抖的葉是我等待的熱情
而當你終於無視地走過
在你身後落了一地的
朋友啊那不是花瓣
是我凋零的心
~~席慕容《一棵開花的樹》~~

小花在國文課讀到這首詩之後非常感動,想要幫教室裡的聖誕樹掛上幾朵花,變成一棵開花的樹。

這棵聖誕樹有一個主幹,主幹上長有若干樹枝,每個樹枝上又再長有一些更小的樹枝,依此類推。主幹和樹枝上都可能長出一至多片葉子。

小花拿了 M 朵花,先全部放在聖誕樹的根部,再一朵一朵掛到上面。每一朵花可以掛在主幹、樹枝或葉子上;樹上的每個地方也可以掛不只一朵花。

當小花掛完 M 朵花以後,覺得這樣還是太單調,不能夠展現她如火的熱情,因此她拿起畫筆,把其中K 朵塗成嬌艷的鮮紅色。然而,小花實在太熱情、用了太多的顏料,顏料就從花上順著樹枝流到了主幹,把所有經過的葉子、樹枝和主幹洗成了紅色。

小明這時候走進了教室,看到小花和鮮紅色聖誕樹,感受到她的熱情,忍不住驚呼「原來· · · · · · 這就是· · · · · · 聖誕紅!」

請問,這棵聖誕紅到底有多紅呢?

Input:

第一行有一整數 T 代表測試資料筆數。兩筆測資之間會以一個空行隔開。

每筆測試資料的第一行有三個整數 N, M, K, N 是聖誕樹主幹、枝幹和葉子的數量總和, M 是花的數量, K 是塗成紅色的花的數量。我們把主幹、樹枝和葉子編號成 1, 2, . . . N ,其中 1 是主幹。接下來有 N 行,用來描述這棵聖誕樹的形狀。這 N 行中的第 i 行一開始有一個數字 ni ,代表第i 號樹枝上長有幾根小樹枝/葉子;後面跟著 ni 個數字分別代表這些小樹枝/葉子的編號,這些數字的順序也是這些小樹枝在第 i 號樹枝上的順序。(若 i = 1 則表示主幹上長的樹枝/葉子,若 ni = 0 則表示第 i 號樹枝其實是一片葉子)

再來有 M 行,第 j 行代表小花掛第 j 朵花的位置。第 j 行一開始有一個數字 mj 後面跟著 mj 個數字 aj,1, aj,2, · · · , aj,mj,這樣表示小花把第 j 朵花掛在主幹的第 aj,1 根樹枝上的第 aj,2 根小樹枝上的第· · · · · · 上的第 aj,mj 根小樹枝/樹葉上。(若 mj = 0 表示這朵花掛在主幹上)

每筆測試資料的最後還有一行,這一行有 K 個數字 f1, f2, . . . , fK,代表小花把這 K 朵花塗成紅色。

Output:

請對每筆測試資料輸出一行,表示被塗成紅色的主幹、枝幹和樹葉的總數。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
3 1 1
2 2 3
0
0
1 1
1

6 2 2
3 2 4 3
0
1 6
0
0
1 5
1 2
2 3 1
2 1

Sample Output :

2
4

Hint :

說明:

第一組測試資料:1 號主幹連到 2 號葉子和 3 號葉子;小花把第一朵花掛在主幹的第一個分枝,也就是 2 號葉子上。第一朵花被塗成紅色,顏料從 2 號葉子流到 1 號主幹,因此 1 號主幹和 2 號葉子都是紅色的,故答案是 2。

第二組測試資料:1 號主幹連到 2 號葉子、4 號葉子和 3 號樹枝, 3 號樹枝連到 6 號樹枝, 6 號樹枝又連到 5 號葉子。小花把第一朵花掛在主幹的第二個分枝,也就是 4 號葉子上;把第二朵花掛在主幹的第三個分枝(3 號樹枝)的第一個分枝,也就是 6 號樹枝上。第二朵花被塗成紅色,顏料從 6 號樹枝流到 3 號樹枝再流到 1 號主幹。第一朵花也被塗成紅色,顏料從 4 號葉子流到 1 號主幹。因此, 1 號主幹、3 號樹枝、4 號葉子、6 號樹枝都是紅色的,故答案是 4。

Author :

NPSC 2010 國中組決賽 (管理員:sagit)

  Solve it!   Status Forum