TopCoder

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

75.0% (3/4)

Tags

Description

你即將在一個特殊場館中舉行一場國際程式競賽,場館可容納 N 個座位,座位們透過 N1 條直接的通路連接著,且保證任意兩個座位都能互相經由若干條通路互相連通。你邀請了 N 位選手,編號為 1N,你也做了一張座位圖,座位圖中每個座位恰好指定一位選手。

場館中的一組座位 S={v1,v2,,v|S|} 可被稱作「道路」,如果存在一組排列 p1,p2,,p|S| 滿足以下條件:

  • 對於所有 1i<|S|,座位 vpivpi+1 之間有直接的通路連接著。
  • 對於所有 |ij|>1,座位 vpivpj 之間沒有直接的通路連接著。

我們說一條道路的 k 個座位 (1kN) 是「美麗的」,如果座位指定在這組的選手編號是 一組連續正整數的排列,即若我們把這 k 個座位上的選手蒐集起來丟進一個序列 B,並加以排序的話,那 B1=B21,B2=B31,,Bi1=Bi1,,B|B|1=B|B|1 將會成立。座位圖的「美麗程度」則是圖中可找出的美麗道路座位組的個數。

你的目標是計算座位圖的「美麗程度」。

Input Format

輸入首行一個正整數 N,變數意義如題目所敘。

接下來 N1 行,每行兩個數字 a,b,代表選手 a 和選手 b 的座位之間有直接的通路連接著。

  • 1N3×105
  • 1a,bN,ab
  • 保證任意兩個座位都能互相經由若干條通路互相連通

Output Format

輸出座位圖的「美麗程度」。

Sample Input 1

8
1 2
2 3
1 6
4 6
5 6
5 8
7 8

Sample Output 1

16

Hints

範測測資一中,形成道路的連續正整數區間分別如下:
[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]

Problem Source

IOICamp 2021 Day3 pA

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資 0
2 0~26 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2
1 3000 262144 65536 2
2 3000 262144 65536 2
3 3000 262144 65536 2
4 3000 262144 65536 2
5 3000 262144 65536 2
6 3000 262144 65536 2
7 3000 262144 65536 2
8 3000 262144 65536 2
9 3000 262144 65536 2
10 3000 262144 65536 2
11 3000 262144 65536 2
12 3000 262144 65536 2
13 3000 262144 65536 2
14 3000 262144 65536 2
15 3000 262144 65536 2
16 3000 262144 65536 2
17 3000 262144 65536 2
18 3000 262144 65536 2
19 3000 262144 65536 2
20 3000 262144 65536 2
21 3000 262144 65536 2
22 3000 262144 65536 2
23 3000 262144 65536 2
24 3000 262144 65536 2
25 3000 262144 65536 2
26 3000 262144 65536 2