A. Сколько независимых множеств

Посчитайте количество допустимых (независимых) множеств вершин дерева по модулю $10^9 + 7$. Пустое множество тоже считается.

Динамика та же, что в классе, но вместо максимума - произведение, а вместо суммы по детям - произведение по детям:

Если $v$ не взята, каждый ребёнок независимо может быть взят или нет. Если взята - ни один ребёнок взят быть не может.

Ответ - $dp[\text{корень}][0] + dp[\text{корень}][1]$.

База: у листа $dp[v][0] = dp[v][1] = 1$ (пустое произведение равно единице).

Проверьте себя на цепочке: у пути из $n$ вершин количество независимых множеств - это числа Фибоначчи. Для $n = 1, 2, 3, 4$ получается 2, 3, 5, 8.

В первой строке - число $n$ ($1 \le n \le 10^5$).

В следующих $n - 1$ строках - рёбра дерева.

Одно число - количество независимых множеств по модулю $10^9 + 7$.