Educational DP Contest AtCoder P - Independent Set

View as PDF
Submit solution
Points: 12
Time limit: 1.0s
Memory limit: 1G
Problem types

There is a tree with N vertices, numbered 1,2,…,N. For each i (1≤i≤N−1), the i-th edge connects Vertex xi and yi.

Taro has decided to paint each vertex in white or black. Here, it is not allowed to paint two adjacent vertices both in black.

Find the number of ways in which the vertices can be painted, modulo 109+7.

Constraints

  • All values in input are integers.
  • 1≤N≤105
  • 1≤xi,yi≤N
  • The given graph is a tree.

Input Specification

The first line will contain the integer N.

The next N−1 lines will each contain 2 space separated integers xi,yi.

Output Specification

Print the number of ways in which the vertices can be painted, modulo 109+7.

Sample Input 1

Copy
3
1 2
2 3

Sample Output 1

Copy
5

Explanation For Sample 1

There are five ways to paint the vertices, as follows:

Sample Input 2

Copy
4
1 2
1 3
1 4

Sample Output 2

Copy
9

Explanation For Sample 2

There are nine ways to paint the vertices, as follows:

Sample Input 3

Copy
1

Sample Output 3

Copy
2

Sample Input 4

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

Sample Output 4

Copy
157

Comments


  • 0
    ExoskeletalPhosphors  commented on Dec. 12, 2020, 1:27 a.m.

    Can we assume the edge goes from xi to yi? (As in, can we assume that the tree functions if you assume all the edges are directed?)


    • 0
      julian33  commented on Dec. 12, 2020, 3:49 p.m.

      The graph is bidirectional.


  • 2
    Medi  commented on Jan. 18, 2019, 5:36 p.m.

    Since it's a single tree, all the vertices will be part of the graph, right?


    • 2
      Kirito  commented on Jan. 18, 2019, 8:29 p.m.

      Yes.