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
Коментарі