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 )