Всем привет! Не могу решить одну задачу на дерево. Надеюсь, что мне сможет кто-нибудь помочь. Дано дерево, необходимо в вершины расставить числа так, чтобы у соседних вершин числа различались(вершины соседние, если между ними есть дуга) и сумма всех чисел была минимальна. Числа от 1 до бесконечности. Кол-во вершин n<10^5 Для ясности намалевал рисунок. Вот линк
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.11.2024 17:56:37 (l3).
Десктопная версия, переключиться на мобильную.
При поддержке
Прикольный рисунок, но его нет)
Запустим как-то dfs. При погружении/возвращении из вершины уменьшаем/увеличиваем текущий ключ. Осталось додумать как лучше это делать.
Меня больше решение интересует, нежели реализация
Тупая же задача...
Заметим, что любое дерево является двудольным графом. Отсюда очевидно, что нам нет смысла использовать числа больше двойки. Т.о. заполним большую долю единицами, меньшую — двойками.
На прилагаемом рисунке граф распадается на две доли размера 6 вершин. По вашему методу ответ 18, а на рисунке ответ 16. Что-то не то.
Да, я бы получил на контесте WA :).
Это было первое, о чем я подумал и даже написал, но в сэмпле меня ждал сюрприз N=8 ребра - 1 2 - 1 3 - 1 4 - 1 5 - 5 6 - 5 7 - 5 8 Верный ответ 11. Ваш алгоритм даст 12. Или я ошибаюсь?
Да, мой жадный алгоритм неправильный.
ОК, тогда можно написать весьма простую динамику. Подвесим дерево за произвольную вершину, и пусть dp[v][num] — минимальная сумма, которую можно получить в поддереве вершины v так, чтобы в вершине v было число num. Считаем динамику очевидным способом: изначально dp[v][num] = num, далее для каждого потомка v2 вершины v выбираем такой num2 != num, что dp[v2][num2] минимально, и прибавляем к dp[v][num].
Каким же должен быть максимальный num? Интуитивно кажется, что 3, но мне это лень доказывать.
Если задача есть в некотором Online Judge я бы попробовал дп с битовыми масками. Есть довольно убедительные полуинтуитивные аргументы указывающие на то, что различных чисел должно быть задействовано немного. Легко видеть, что порядок меньше корня. Полагаю даже меньше либо равно логарифма. Четко доказать не могу, но есть некоторая конструкция показывающая что с ростом количества различных чисел число вершин должно серьезно возрастать. Рядом с вершиной в которой мы пишем 4 должны располагаться поддеревья, в которых есть вершины 3, 2, 1. рядом с вершиной, в которой мы пишем 5, должны располагаться другие поддеревья, в которых есть вершины 4, 3, 2, 1, ну и и т.д. Как было замечено граф двудольный. Я это не заметил сразу, подумал лишь что планарный, поэтому 4-х красок хватит, но вот что их хватит для минимальности сомневаюсь. Вроде бы этому строится контр-пример конструкцией чуть выше. Можно попровать дп, изменяя масимальное число различных чисел вверх, по мере получения WA, или подумать как строить жадно начиная с листьев дерева, и перекрашивая потом некоторые объединяемые поддеревья, если это становится выгодно.
А, гоню. Нам ведь и не нужны никакие маски. Достаточно знать число, которое стоит в вершине поддерева, и общую сумму в поддереве.
Поправлюсь, правильнее сказать "не более корня". А объединение по дп простое, для детей той вершины куда мы щас ставим число числа в вершинах могут и совпадать, поэтому просто запоминаем для каждого ребёнка два минимума, перебираем то что ставим в вершине и выбираем минимум не равный текущему числу в вершине.
Именно логарифма.
Если в минимальной нумерации есть число k, то это означает, что с ним смежны вершины с числами 1, 2, ..., k - 1. Пусть минимальное число вершин, которые должны висеть на вершине "k - 1", чтобы было необходимо поставить именно k - 1, равно fk - 1. Но на самом деле причина, по которой необходимо поставить именно k - 1 — это то, что на этой вершине уже висят вершины со всеми меньшими номерами. Так что, fk - 1 — это как раз то количество вершин, которое нужно, чтобы на вершине k - 1 висели вершины 1, 2, ..., k - 2. Получается, что на вершине k должны висеть как минимум 2fk - 1 + 1 вершина.