4-й этап Республиканской олимпиады по информатике 2019, 10-11 класс
Задача D. Дерево невидимого Жанадиля
Ограничение по времени:
2 секунды
Ограничение по памяти:
256 мегабайт
Дано связное дерево с N вершин. Невидимый Жанадиль выбирает какое-то подмножество вершин из заданного дерева, и удаляет все выбранные вершины и связанные с ними ребра из дерева. В результате получится лес из X связанных компонент, где компонента i содержит szi вершин, для 1<=i<=X. Основываясь на этом, Жанадиль считает значение F=X∑i=12sz[i]. Ваша задача состоит в том чтоб посчитать и вывести сумму значений F по всем возможным подмножествам. Выведите ответ по модулю 109+7.
Формат входного файла
Первая строка содержит целое число N (1<=N<=2∗105) — количество вершин в дереве.
Каждая из следующих N−1 строк содержит два целых числа ui и vi (1<=ui<=N, 1<=vi<=N и ui≠vi) — ребро дерева между вершинами ui и vi.
Формат выходного файла
Выведите сумму значений F по всем возможным подмножествам по модулю 109+7.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются дополнительные ограничения:
- 1<=N<=20. Оценивается в 8 баллов.
- 1<=N<=200. Оценивается в 13 баллов.
- 1<=N<=2000. Оценивается в 18 баллов.
- 1<=N<=2∗105, у каждой вершины не более двух соседей. Оценивается в 14 баллов.
- Ограничения из условия. Оценивается в 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+2∗3+4∗3+8=26.
(
Nurbakyt Madibek
)
Комментарий/решение:
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.