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


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

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

Дано связное дерево с $N$ вершин. Невидимый Жанадиль выбирает какое-то подмножество вершин из заданного дерева, и удаляет все выбранные вершины и связанные с ними ребра из дерева. В результате получится лес из $X$ связанных компонент, где компонента $i$ содержит $sz_i$ вершин, для $1 <= i <= X$. Основываясь на этом, Жанадиль считает значение $$F = \sum_{i=1}^{X} 2^{sz[i]}$$. Ваша задача состоит в том чтоб посчитать и вывести сумму значений $F$ по всем возможным подмножествам. Выведите ответ по модулю $10^9 + 7$.
Формат входного файла
Первая строка содержит целое число $N$ $(1 <= N <= 2 * 10^5)$ — количество вершин в дереве. Каждая из следующих $N - 1$ строк содержит два целых числа $u_i$ и $v_i$ ($1 <= u_i <= N$, $1 <= v_i <= N$ и $u_i \neq v_i$) — ребро дерева между вершинами $u_i$ и $v_i$.
Формат выходного файла
Выведите сумму значений $F$ по всем возможным подмножествам по модулю $10^9 + 7$.
Система оценки
Данная задача содержит пять подзадач, в каждой подзадаче выполняются дополнительные ограничения:
  1. $1 <= N <= 20$. Оценивается в 8 баллов.
  2. $1 <= N <= 200$. Оценивается в 13 баллов.
  3. $1 <= N <= 2000$. Оценивается в 18 баллов.
  4. $1 <= N <= 2 * 10^5$, у каждой вершины не более двух соседей. Оценивается в 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 + 2 * 3 + 4 * 3 + 8 = 26$. ( Nurbakyt Madibek )
посмотреть в олимпиаде

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