## Independent Set

View as PDF

Points: 12 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

These problems are from the atcoder DP contest, and were transferred onto DMOJ. All problem statements were made by several atcoder users. As there is no access to the test data, all data is randomly generated. If there are issues with the statement or data, please contact Rimuru or Ninjaclasher on slack.

There is a tree with vertices, numbered . For each , the -th edge connects Vertex and .

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 .

#### Constraints

• All values in input are integers.
• The given graph is a tree.

#### Input Specification

The first line will contain the integer .

The next lines will each contain 2 space separated integers .

#### Output Specification

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

#### Sample Input 1

3
1 2
2 3

#### Sample Output 1

5

#### Explanation For Sample 1

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

#### Sample Input 2

4
1 2
1 3
1 4

#### Sample Output 2

9

#### Explanation For Sample 2

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

#### Sample Input 3

1

#### Sample Output 3

2

#### Sample Input 4

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

#### Sample Output 4

157

• commented on Dec. 11, 2020, 8:27 p.m.

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

• commented on Dec. 12, 2020, 10:49 a.m.

The graph is bidirectional.

• commented on Jan. 18, 2019, 12:36 p.m.

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

• commented on Jan. 18, 2019, 3:29 p.m.

Yes.