Independent Set - 题目详情 - Hydro

ID: 3735

传统题

1000ms

128MiB

难度: 10

上传者:

Description

给一棵树，每一个点可以染成黑色或白色，任意两个相邻节点不能都是黑色，求方案数，结果对 1e9+7 取模。

Input Format

第一行输入一个数n，表示顶点的个数。(1<=n<=1e5)
接下来输入n-1行，每行包括一条边连接的两个相邻节点。

Output Format

总的方案数，结果对 1e9+7取模。

3
1 2
2 3

Source

树形dp