Count Tree Nodes Greater Than Every Cross-Subtree Pair Sum and Product

Given a binary tree of integers, count the nodes whose value is larger than every sum and every product that can be formed by taking one value from the node's left subtree and one value from its right subtree. The comparison uses the node's entire left and right subtrees, not only its direct children. The candidate's report describes the test only as comparing the sum and the product of one value from each subtree with the node's value; this version fixes the exact rule in Rules below. ### Function Signature ```python def count_dominant_nodes(tree: list[int | None]) -> int: ``` ### Rules - `tree` is the level-order (breadth-first, left to right) listing of the nodes. Each existing node's two child slots appear in order, with `None` for a missing child; a missing node has no child slots. Trailing `None` entries may be omitted. `tree[0]` is the root and is never `None`. - For a node with value `v`, let `L` be the values in its entire left subtree and `R` the values in its entire right subtree. - The node is counted when both `L` and `R` are nonempty and, for every pair with `a` taken from `L` and `b` taken from `R`, both `a + b < v` and `a * b < v` hold. Both inequalities are strict. - A node whose left subtree or right subtree is empty, including every leaf, is never counted. - Return the number of counted nodes as a single integer. ### Constraints - `1 <= number of nodes <= 10^4` - `-10^4 <= node value <= 10^4`; values may be negative, zero or repeated. - Every sum and product of two node values lies within `[-10^8, 10^8]`. - The tree is not necessarily balanced; its height can be as large as the number of nodes. ### Examples **Example 1** ```text Input: tree = [8, 3, 4, 1, 1] Output: 1 ``` ```text 8 / \ 3 4 / \ 1 1 ``` Node 3 has `L = {1}` and `R = {1}`: `1 + 1 = 2 < 3` and `1 * 1 = 1 < 3`, so it is counted. For the root, `L = {3, 1, 1}` and `R = {4}`; every sum is at most `3 + 4 = 7 < 8`, but the product `3 * 4 = 12` is not less than 8, so the root is not counted. Node 4 and the two leaves have an empty subtree. **Example 2** ```text Input: tree = [5, -3, -2] Output: 0 ``` The root's only pair is `(-3, -2)`: the sum `-5` is less than 5, but the product `6` is not. The two children are leaves. **Example 3** ```text Input: tree = [20, -6, 3, -7, 1, None, 2] Output: 1 ``` ```text 20 / \ -6 3 / \ \ -7 1 2 ``` For the root, `L = {-6, -7, 1}` and `R = {3, 2}`. The largest pair sum is `1 + 3 = 4` and the largest pair product is `1 * 3 = 3`, both below 20, so the root is counted. Node -6 has the single pair `(-7, 1)`, whose sum `-6` is not strictly less than `-6`, so it is not counted. Node 3 has no left subtree, and the remaining nodes are leaves.