10716: Незалежна множина


Відправити розв'язок

Бали: 100 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Brain****, C++, Java, Pascal, Python, v8js

Дано дерево з \(N\) вершин. Скільки є способів розфарбувати вершини дерева в білий та чорний кольори так, щоб в дереві не було двох суміжних чорних вершин?

Формат вхідних даних

В першому рядку ціле число \(N\) (\(1 \le N \le 10^5\))
В наступних \(N-1\) рядках міститься по два числа \(V1,V2\) - що описують ребра дерева.

Формат вихідних даних

Виведіть кількість способів за модулем \(10^9+7\)

Приклад вхідних даних-1

3
1 2
2 3

Приклад вихідних даних-1

5

Пояснення до прикладу-1

Приклад вхідних даних-2

4
1 2
1 3
1 4

Приклад вихідних даних-2

9

Пояснення до прикладу-2

Приклад вхідних даних-3

1

Приклад вихідних даних-3

2

Приклад вхідних даних-4

10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Приклад вихідних даних-4

157

Коментарі

Ще немає коментарів.