2016年2月4日 星期四

[IOI Camp Judge 53]鋪路問題 (題目備份)

IOI Camp Judge是暫時性的,因此在這裡做題目備份
題解在這裡,我也很克難的寫出了動態樹做法

鋪路問題

Time Limit: 3s

Description


你是一個國家的交通部長,你們國內總共有  座城市,城市間總共有  條道路,每條道路都爲雙向通行,但有些城市卻無法透過現有的道路到其他城市,而對於可以兩兩透過道路通往彼此的城市,我們稱爲城市群。如果一個城市群在加入其他城市後,不再是一個城市群,則稱之爲極大城市群。而這些道路中,又有一些道路是特別重要的,我們稱爲重要道路,重要道路的定義爲:如果把重要道路拔除,則國家內的極大城市群數量會增加。
身爲交通部長,你想改善國內的交通狀況,因此,你決定再建造  條道路,而且你想知道新建造的這些道路對現有交通狀況的影響,因此,你決定找出每建造一條道路後,國內總共的重要道路數。

Input Format


第一行有一個正整數 ,代表總共有幾筆測試資料。每筆測試資料第一行包含兩個正整數 ,代表國內的城市數以及現有的道路數。接下來包含  行,每行兩個正整數 ,代表存在城市  到城市  的雙向道路。接下來一行包含一個正整數 ,代表預計新建造的道路數。接下來包含  行,每行兩個正整數 ,代表新建造的雙向道路連接城市  及城市 

Output Format


對於每筆測試資料,請輸出  行,每行一個整數,代表每建造完一條道路後,國內的重要道路數。

Sample Input


1
3 0
3
1 2
2 3
1 3

Sample Output


1
2
0

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原