Loading [MathJax]/jax/output/SVG/jax.js

4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс


Задача D. Дерево невидимого Жанадиля

Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт

Дано связное дерево с N вершин. Невидимый Жанадиль выбирает какое-то подмножество вершин из заданного дерева, и удаляет все выбранные вершины и связанные с ними ребра из дерева. В результате получится лес из X связанных компонент, где компонента i содержит szi вершин, для 1<=i<=X. Основываясь на этом, Жанадиль считает значение F=Xi=12sz[i]. Ваша задача состоит в том чтоб посчитать и вывести сумму значений F по всем возможным подмножествам. Выведите ответ по модулю 109+7.
Формат входного файла
Первая строка содержит целое число N (1<=N<=2105) — количество вершин в дереве. Каждая из следующих N1 строк содержит два целых числа ui и vi (1<=ui<=N, 1<=vi<=N и uivi) — ребро дерева между вершинами ui и vi.
Формат выходного файла
Выведите сумму значений F по всем возможным подмножествам по модулю 109+7.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются дополнительные ограничения:
  1. 1<=N<=20. Оценивается в 8 баллов.
  2. 1<=N<=200. Оценивается в 13 баллов.
  3. 1<=N<=2000. Оценивается в 18 баллов.
  4. 1<=N<=2105, у каждой вершины не более двух соседей. Оценивается в 14 баллов.
  5. Ограничения из условия. Оценивается в 47 баллов.
Примеры:
Вход
3
1 2
2 3
Ответ
26
Вход
5
1 2
1 3
5 1
5 4
Ответ
216
Замечание
В первом примере из условия сушествует 8 различных возможных подмножеств, F приобретает значения: 0, 2, 2, 2, 4, 4, 4, 8. Сумма этих значений равна 0+23+43+8=26. ( Nurbakyt Madibek )
посмотреть в олимпиаде

Комментарий/решение: