아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Дерево

시간 제한2초메모리 제한1024 MB

요약
N개의 정점과 N-1개의 간선으로 하나 이상의 루트 트리를 만들어 잎 깊이 합의 총합이 최대가 되도록 한다.
난이도

보통10점 중 4점

유형
트리, 수학, 그리디
정답자
아직 제출이 없습니다

문제

Остап Бендер нашел новое применение своим безграничным талантам, а имненно, решил удариться в бизнес. На современном рынке полно всяких товаров, однако его это не смущает, ведь он торгует не чем-нибудь, а корневыми деревьями.

Всем известно, что цена корневого дерева --- это сумма глубин его листов. Корень дерева имеет глубину 0, а глубина любой другой вершины равна глубине ее предка плюс один. У Остапа никогда не возникало проблем с тем, чтобы определить цену дерева, глядя на него, но вот строить дорогие деревья он не умеет.

У нашего героя есть NN вершин, и целых N−1N-1 ребро. Он может построить из них одно, или несколько деревьев, а потом продать. Помогите Остапу, найдите максимальную суммарную стоимость построеных деревьев.

입력

Первая строка входного файла содержит единственное число NN (1≤N≤8,589,934,5911\le N\le 8{\\,}589{\\,}934{\\,}591) --- количество вершин, которые есть у Остапа.

출력

Выведите одно число --- максимальная суммарная цена построеных деревьев.

힌트

В этом примере можно обойтись одним деревом. Пусть корнем дерева будет вершина 1, тогда выгодно провести ребра 1→21 \to 2 и 1→31 \to 3. Стоимость дерева --- сумма глубин второй и третьей веришины --- 1+1=21 + 1 = 2.

Листом дерева называется вершина, соединенная только со своим предком.

예제1

  1. 예제 1

    입력
    3
    
    예상 출력
    2