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 )
посмотреть в олимпиаде

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