You are given a binary tree containing n nodes. Count the subsets of nodes in which no two selected nodes are directly connected by an edge.

The empty subset is valid. Return the total number of valid subsets modulo 1,000,000,007.

Each node is represented by a string in the format "nodeId,value,leftChildId,rightChildId". A child identifier of -1 means that the corresponding child does not exist.

Class

BinaryTreeSubsetCounter

Method

countValidSubsets

public int countValidSubsets(List<String> nodes, int rootId)

• nodes contains the node identifiers, values, and child relationships of the binary tree.
• rootId is the identifier of the root node.
• Returns the number of valid subsets modulo 1,000,000,007.

Rules

• A node may either be selected or excluded from a subset.
• A selected node and its parent cannot both belong to the same subset.
• Nodes that are not directly connected may be selected together.
• The empty subset is included in the answer.
• Subsets are distinguished by node identifiers, even when nodes have equal values.
• Node values do not affect whether a subset is valid.
• The node records may appear in any order.
• The supplied list must not be modified.

Constraints

• n = nodes.size()
• 1 ≤ n ≤ 200,000
• Every element of nodes contains exactly four comma-separated integers in the format "nodeId,value,leftChildId,rightChildId".
• 1 ≤ nodeId ≤ 1,000,000,000
• -1,000,000,000 ≤ value ≤ 1,000,000,000
• Every nodeId is unique.
• Each child identifier is either -1 or the identifier of another node in nodes.
• rootId is the identifier of exactly one node in nodes.
• The supplied records form a valid binary tree rooted at rootId.
• Every node other than the root is referenced exactly once as a child.
• The expected time complexity is O(n).

Examples

Example 1

countValidSubsets(nodes = ["10,8,20,30", "20,4,40,-1", "30,9,-1,-1", "40,6,-1,-1"], rootId = 10)

Output: 8

The edges are 10-20, 10-30, and 20-40. There are eight subsets containing no two endpoints of the same edge.

Example 2

countValidSubsets(nodes = ["5,12,2,9", "2,4,1,3", "9,20,7,11", "1,6,-1,-1", "3,8,-1,-1", "7,15,-1,-1", "11,25,-1,-1"], rootId = 5)

Output: 41

The tree is a perfect binary tree with seven nodes. It has 41 valid subsets, including the empty subset.

Example 3

countValidSubsets(nodes = ["100,3,200,-1", "200,5,-1,300", "300,7,400,-1", "400,11,-1,500", "500,13,-1,-1"], rootId = 100)

Output: 13

The five nodes form a single chain. The chain has 13 subsets in which no adjacent nodes are selected.

Example 4

countValidSubsets(nodes = ["77,25,-1,-1"], rootId = 77)

Output: 2

A single-node tree has two valid subsets: the empty subset and the subset containing the node.