你即將在一個特殊場館中舉行一場國際程式競賽,場館可容納 N 個座位,座位們透過 N−1 條直接的通路連接著,且保證任意兩個座位都能互相經由若干條通路互相連通。你邀請了 N 位選手,編號為 1 到 N,你也做了一張座位圖,座位圖中每個座位恰好指定一位選手。
場館中的一組座位 S={v1,v2,⋯,v|S|} 可被稱作「道路」,如果存在一組排列 p1,p2,⋯,p|S| 滿足以下條件:
我們說一條道路的 k 個座位 (1≤k≤N) 是「美麗的」,如果座位指定在這組的選手編號是 一組連續正整數的排列,即若我們把這 k 個座位上的選手蒐集起來丟進一個序列 B,並加以排序的話,那 B1=B2−1,B2=B3−1,…,Bi−1=Bi−1,…,B|B|−1=B|B|−1 將會成立。座位圖的「美麗程度」則是圖中可找出的美麗道路座位組的個數。
你的目標是計算座位圖的「美麗程度」。
輸入首行一個正整數 N,變數意義如題目所敘。
接下來 N−1 行,每行兩個數字 a,b,代表選手 a 和選手 b 的座位之間有直接的通路連接著。
輸出座位圖的「美麗程度」。
範測測資一中,形成道路的連續正整數區間分別如下: [1,1],[1,2],[1,3],[2,2],[2,3],[3,3],[4,4],[4,6], [4,8],[5,5],[5,6],[5,8],[6,6],[7,7],[7,8],[8,8]
IOICamp 2021 Day3 pA