hackercupai/hackercup huggingface dataset:
We'll define a "region" as a set of _"*"_ nodes reachable from one another without passing through _"#"_ nodes, and the size of a region as the number of nodes in it. We'll then let \(C_i\) be the size of node \(i\)'s region (with \(C_i = 0\) if \(S_i\) = _"#"_). The regions and \(C\) values may all be computed in \(O(N)\) time using floodfill (DFS). We can also compute the initial number of safely-reachable node pairs — each region having size \(s\) contributes \(s(s-1)/2\) such pairs.

We'll consider each non-root node \(i\) such that the edge between \(i\) and \(E_i\) will be deleted. For now, we'll ignore the case in which there are fewer than two regions, and return to it later. When there are at least two regions, we should only consider edges that won't break up a region (that is, nodes \(i\) such that \(S_i\) = _"#"_ and/or \(S_{E_i}\) = _"#"_). Let's say that the maximum \(C\) value within \(i\)'s subtree is \(m_1\), and there are \(q_1\) nodes in \(i\)'s subtree with that \(C\) value. Let's similarly define \(m_2\) and \(q_2\) for nodes outside \(i\)'s subtree. An edge insertion can then contribute up to \(m_1 m_2\) additional safely-reachable node pairs on top of the initial number, and there are \(q_1 q_2\) edge insertions for which that's the case.

Returning to the case in which there's at most one region, essentially the only difference is that we may consider deleting any edge. If we delete one between two _"*"_ nodes (thus breaking up the single region), we must ensure that an edge is then inserted between two nodes with non-zero \(C\) values (very similar to the above, except noting that there will be no additional safely-reachable node pairs on top of the initial number). If we delete a different edge, then *any* edge may be inserted (between a node within \(i\)'s subtree and a node outside it).

Each of the values required above (such as \(m_1\), \(q_1\), \(m_2\), and \(q_2\)) may be obtained in constant time after a \(O(N)\) precomputation process. In particular, we'll begin by performing a pre-order traversal of the tree while numbering the nodes in that order and storing the range of nodes included in each node's subtree (which must be a contiguous subarray of this ordering). Then, for each prefix and suffix of this ordering, as well as for each subtree's subarray, we'll compute two values: the maximum \(C\) value present amongst those nodes, and the number of those nodes having that \(C\) value.

As such, the time complexity of this solution comes out to \(O(N)\).