Pinely Round 2 (Div. 1 + Div. 2) |
---|
Закончено |
Дано дерево из $$$n$$$ вершин, пронумерованных числами $$$1, 2, \ldots, n$$$. Длина простого пути в дереве равна числу вершин в нём.
Вам нужно выбрать некоторое множество простых путей длины хотя бы $$$2$$$ каждый, причём нельзя одновременно выбрать два разных пути, один из которых содержится в другом. Найдите наибольший возможный размер такого множества.
Формально, множество вершин $$$S$$$ называется маршрутом, если в нём по крайней мере две вершины, при этом оно является множеством вершин некоторого простого пути в дереве. Набор попарно различных маршрутов называется расписанием. Маршрут $$$S$$$ в расписании $$$T$$$ называется избыточным, если есть какой-то другой маршрут $$$S' \in T$$$, такой что $$$S \subset S'$$$. Расписание называется эффективным, если в нём нет избыточных маршрутов. Найдите наибольшее возможное количество маршрутов в эффективном расписании.
Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 3000$$$).
Далее следуют $$$n - 1$$$ строк, $$$i$$$-я из которых содержит два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \neq v_i$$$) — номера вершин, соединённых $$$i$$$-м ребром.
Гарантируется, что заданные ребра образуют дерево.
Выведите единственное число — ответ на задачу.
4 1 2 1 3 1 4
3
7 2 1 3 2 4 3 5 3 6 4 7 4
7
В первом примере возможными эффективными расписаниями являются $$$\{\{1, 2\}, \{1, 3\}, \{1, 4\}\}$$$ и $$$\{\{1, 2, 3\}, \{1, 2, 4\}, \{1, 3, 4\}\}$$$.
Во втором примере можно выбрать $$$\{ \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 6\}, \{2, 3, 5\}, \{3, 4, 5\}, \{3, 4, 7\}, \{4, 6, 7\}\}$$$.
Название |
---|