Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ML2_D - Skracanie ścieżek

Dane jest drzewo o n wierzchołkach i n-1 krawędziach. Krawędzie są nieskierowane, każda z nich ma długość 1.

Jan postanowił zmodyfikować graf. Stworzył listę wszystkich ścieżek o długości 2 znajdujących się w drzewie. Następnie dla każdej ścieżki u - w - v, gdzie u, w, v to wierzchołki drzewa, dodał nieskierowaną krawędź o długości 1 pomiędzy wierzchołkami u i v.

Odpowiedz na pytanie, jaka jest suma najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w nowo powstałym grafie?

Wejście

W pierwszej linii wejścia znajduje się liczba wierzchołków n ∈ [2, 105]. W kolejnych n-1 liniach znajdują się opisy krawędzi.

Opis każdej krawędzi składa się z dwóch liczb naturalnych u, v (1 ≤ u, vn; uv) określających numery wierzchołków, które są ze sobą połączone.

Wyjście

Na wyjściu należy wypisać odpowiedź na pytanie, jaka jest suma najkrótszych ścieżek pomiędzy wszystkimi parami wierzchołków w nowo powstałym grafie.

Przykład

Wejście:

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

Wyjście:

68

Dodane przez:Maciej Boniecki
Data dodania:2019-07-29
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Mini Liga 2

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.