Bear and Almost Row
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Bearland has N cities, numbered 1 through N. For every i between 1 and N-1 inclusive, there is a road between cities i and i+1. There K extra roads: the i-th of them connects two different cities ai and bi. So, there are N-1+K roads in total. All roads are bidirectional.
You can assume that every two cities are connected by at most one road.
Let f(s, t) denote the distance between cities s and t, i.e. the minimum possible number of roads needed to get from one city to the other.
Your task is to find the sum of f(s, t) over all pairs of cities (s, t) such that s < t.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains an integer N denoting the number of cities.
The second line contains an integer K denoting the number of extra roads. Note the unusual constraint for K (in the constraints section below).
The i-th of the following K lines contains two different integers ai and bi, denoting cities connected by the i-th road. All N-1+K roads will be distinct.
For each test case, output a single line containing one integer — the sum of f(s, t) over all pairs (s, t) such that s < t. For the given constraints, it can be proved that the answer fits in the 64-bit signed type.
- 1 ≤ T ≤ 1000
- 2 ≤ N ≤ 106
- 0 ≤ K ≤ 10
- 1 ≤ ai, bi ≤ N
- ai ≠bi
- All N-1+K roads will be distinct.
- Subtask #1 (15 points): 2 ≤ N ≤ 40
- Subtask #2 (35 points): The sum of N in all test cases won't exceed 200,000.
- Subtask #3 (15 points): 0 ≤ K ≤ 1
- Subtask #4 (35 points): Original constraints.
Input: 4 4 2 1 3 4 1 5 1 2 5 20 3 1 7 3 12 17 19 1000000 0 Output: 7 16 891 166666666666500000
The provided example test contains T = 4 test cases. The following drawings show the situation for the first two test cases (extra roads are red):
In the first test case, there are 4 cities and 2 extra roads 1-3 and 4-1. So we have 5 roads in total: 1-2, 1-3, 1-4, 2-3, 3-4 (see the left drawing). The sought values are:
- f(1, 2) = f(1, 3) = f(1, 4) = f(2, 3) = f(3, 4) = 1
- f(2, 4) = 2
The answer is 1 + 1 + 1 + 1 + 1 + 2 = 7.
|Tags||errichto, floyd-warshall, hard, ltime46, shortest-path|
|Time Limit:||2.5 - 7 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.