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

Есеп D. Көрінбейтін Жанәділдің ағашы

Ограничение по времени:

2 seconds

Ограничение по памяти:

256 megabytes

Көрінбейтін Жанәділ осы есепті шығарғысы келеді: $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 )