Дерево
시간 제한2초메모리 제한1024 MB
N개의 정점과 N-1개의 간선으로 하나 이상의 루트 트리를 만들어 잎 깊이 합의 총합이 최대가 되도록 한다.
문제
Остап Бендер нашел новое применение своим безграничным талантам, а имненно, решил удариться в бизнес. На современном рынке полно всяких товаров, однако его это не смущает, ведь он торгует не чем-нибудь, а корневыми деревьями.
Всем известно, что цена корневого дерева --- это сумма глубин его листов. Корень дерева имеет глубину 0, а глубина любой другой вершины равна глубине ее предка плюс один. У Остапа никогда не возникало проблем с тем, чтобы определить цену дерева, глядя на него, но вот строить дорогие деревья он не умеет.
У нашего героя есть вершин, и целых ребро. Он может построить из них одно, или несколько деревьев, а потом продать. Помогите Остапу, найдите максимальную суммарную стоимость построеных деревьев.
입력
Первая строка входного файла содержит единственное число () --- количество вершин, которые есть у Остапа.
출력
Выведите одно число --- максимальная суммарная цена построеных деревьев.
힌트
В этом примере можно обойтись одним деревом. Пусть корнем дерева будет вершина 1, тогда выгодно провести ребра и . Стоимость дерева --- сумма глубин второй и третьей веришины --- .
Листом дерева называется вершина, соединенная только со своим предком.