回分類題庫
h197: A.分裂的樹堆
關鍵字: NPSC 2018 高中組決賽

測資點 : 5 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 5 Times / 3 Users | Submit : 17 Times / 5 Users | Accepted rate : 60%
題目加入時間 : 2020-05-13 14:22

Content: 简体中文

讓我們再次回到中古時期之後的一段時間,人們把他稱之為後古時期,介紹一個樹堆國遇到的問題。

由於在中古時期時社會對「樹」的重視,以至於後古時期社會上處處都看的到以「樹」的形狀為藍圖發展形成的都市。同樣的,樹堆國也有相同的設計,樹堆國是由 N 個聚落以及 N − 1 條道路組成,每個聚落都被給予了一個從 1 到 N 不同的編號,每一條道路都連接著兩個不相同的聚落。並且對於任兩個不相同的聚落,在不經過相同道路的條件下,都存在恰一種的抵達方法。而若兩個聚落可以透過道路抵達彼此,則稱兩個聚落在同一個連通塊。

在後古時期時,因為社會逐漸腐敗,從而引發了樹藝復興運動,思想家開始反對中古時期的樹堆觀,科學家懷疑⻑期以來居於宗教統治地位的樹心說,觀察到萬物並不是繞著樹堆旋轉的,激進派甚至組織⺠眾試圖以革命顛覆傳統裡樹堆對社會造成的巨大影響。

激進派分子已經計畫好了一條路徑,他們打算從聚落編號 S 出發並不重複經過同一條道路的抵達聚落編號 T 。並且拆除沿途經過的道路,使這些道路從樹堆國裡消失,從此讓大地四分五裂,讓綠意盎然的樹堆國不復存在,讓樹堆思想不能傳遞到樹堆國的灰色邊陲地帶。

很快的這個計畫被樹論專家得知,但他們只知道革命路徑的起點 S ,對於終點他們只知道路徑終點 T 是介於編號 L 到編號 R 的聚落。面對激進派分子的計畫,樹論專家定義了慘度來衡量激進派暴動後所造成的破壞程度:慘度的值為在激進派分子拆除經過的道路後樹堆國的連通塊數量。接著樹論專家一籌莫展,面對即將分裂的王國,樹堆的平衡將受到挑戰。

所以專家找上了致力於恢復古樹堆的光榮的你,請你幫忙計算對於激進派分子所有可能的計畫總共 R − L + 1 種路線會造成的慘度總和有多少? 

Input:

測試資料第一行包含一個正整數 T,表示總共有幾組測試資料。

每組測試資料第一行包含一個正整數 N,表示樹堆圖的點數。

接下來第二行包含三個數字正整數 S, L, R,分別表示激進派分子計畫路徑的起點,以及路徑終點的左界、右界,意義如題目所述。

接下來有 N − 1 行描述樹堆國的每一條邊,第 i 行有兩個整數 ai, bi,代表第 i 邊連結著聚落 ai 和聚落 bi。 

Output:

針對每組測試資料,請輸出一個數字代表對於所有可能的計畫會造成的慘度總和。

Sample Input:help

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

Sample Output :

1
3

Hint :

Author :

NPSC 2018 高中組決賽 (管理員:sagit)

  Solve it!   Status Forum