16263번 - Red-Black Tree 다국어

Did you now that most standard libraries use red-black tree to implement "set" data structure? In this problem you have to find the number of ways to color the vertices of the given binary tree so that it became red-black. Print the answer modulo 10⁹ + 7.

Consider a binary tree. If the vertex has less than two children, add fake vertices to the potential places of the missing children. The tree is called a red-black tree if the following constraints are satisfied:

1. Each vertex is colored one of the two colors: red or black.
2. The root of the tree and added fake vertices are colored black.
3. The parent of a red vertex is black.
4. All paths the root to fake leafs contain the same number of black vertices.

Note that the parent of a black vertex can be black itself.

Two ways to color the tree are different if there is a vertex that has different colors.

The picture shows two ways to color the tree from the second test case.

The first line contains one integer n — the number of vertices in a tree (1 ≤ n ≤ 500 000).

The following n lines describe a tree. The i-th of these lines contains two integers l_i and r_i — the indices of the left and the right child of the i-th vertex, or 0 if the corresponding child is missing (l_i = 0 or i < l_i ≤ n; r_i = 0 or i < r_i ≤ n). The root of the tree has number 1. Input describes the correct tree.

Output one integer — the number of ways to color the given tree so that it was a correct red-black tree. The answer must be printed modulo 10⁹ + 7.