575. How Many Sets Have No Two Neighbours
Count the sets of nodes with NO two of them joined by an edge. The empty set counts, and so
does every single node. Print the count modulo 1000000007.
2 nodes joined by an edge -> 3 {}, {1}, {2}
4 nodes, edges 1-2 1-3 3-4 -> 8
## The same recurrence as 566, with a different operator
Problem 566 asked for the BEST such set. This asks how MANY there are. The two share their entire structure, and the only changes are:
max becomes + choosing between options becomes adding their counts
+ becomes * combining independent children becomes multiplying
That substitution is the whole lesson. An optimisation over a set of choices and a count of that same set differ only in which pair of operators is used to fold them together, and the recurrence itself does not move.
## The two numbers
take[u] = how many valid sets in u's subtree include u
skip[u] = how many valid sets in u's subtree exclude u
If u is in the set, no child may be, so each child contributes exactly skip[c] ways:
take[u] = product over children c of skip[c]
If u is out, each child is free either way, giving take[c] + skip[c] ways:
skip[u] = product over children c of (take[c] + skip[c])
Both empty products are 1, so a leaf has take = 1 and skip = 1: the set {leaf} and the
empty set.
The answer is take[root] + skip[root], reduced.
## Why multiplication is allowed
Two children's subtrees share no node and no edge, so a choice inside one places no restriction on the other. Independent choices multiply. If the subtrees could interact, this recurrence would overcount, and that is the first thing to check whenever a counting DP gives a number that is too large.
## Where the modulus goes
Reduce after EVERY multiplication and every addition, not once at the end. A product of two
numbers below 10^9 reaches nearly 10^18, which fits in 64 bits, but a second multiplication
without reducing does not.
In JavaScript the same product exceeds the exact integer range of a double, so use big integers or a multiplication routine that reduces as it goes.
## Boundaries
A single node answers 2: the empty set and {1}.
A star of eight nodes answers 129: either the centre alone, or any of the 2^7 subsets of the
leaves.
## Cost
Time O(n). Space O(n).
Constraints - `1 ≤ n ≤ 100000` - the input is always a tree
Input
The first line contains an integer n, the number of nodes.
Each of the next n - 1 lines contains two integers u and v, an edge of
the tree. Nodes are numbered 1 to n and the tree is rooted at node 1.
Output
Print one integer, the number of sets with no two adjacent nodes, modulo 1000000007.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.