| English | 简体中文 |
You are given an array
pairs[i] = [xi, yi], and:
- There are no duplicates.
xi < yi
ways be the number of rooted trees that satisfy the following conditions:
- The tree consists of nodes whose values appeared in
- A pair
[xi, yi]exists in
pairsif and only if
xiis an ancestor of
yiis an ancestor of
- Note: the tree does not have to be a binary tree.
Two ways are considered to be different if there is at least one node that has different parents in both ways.
ways == 0
ways == 1
ways > 1
A rooted tree is a tree that has a single root node, and all edges are oriented to be outgoing from the root.
An ancestor of a node is any node on the path from the root to that node (excluding the node itself). The root has no ancestors.
Input: pairs = [[1,2],[2,3]] Output: 1 Explanation: There is exactly one valid rooted tree, which is shown in the above figure.
Input: pairs = [[1,2],[2,3],[1,3]] Output: 2 Explanation: There are multiple valid rooted trees. Three of them are shown in the above figures.
Input: pairs = [[1,2],[2,3],[2,4],[1,5]] Output: 0 Explanation: There are no valid rooted trees.
1 <= pairs.length <= 105
1 <= xi < yi <= 500
- The elements in