hackercupai/hackercup huggingface dataset:
The network of plants can be thought of as a tree, which we can arbitrarily root at node (plant) \(1\). We can then observe that an edge (road) between a node \(i\) and its parent node \(P_i\) (if any) may be blockaded if and only if, for each frequency \(f\), either *all* or *none* of the nodes which have a frequency of \(f\) are located within \(i\)'s subtree. Otherwise, there would be at least one pair of nodes with frequency \(f\) (with one inside \(i\)'s subtree and one outside it) which would become inaccessible if the edge in question were blockaded. Note that these condition are independent per edge. What remains is checking these conditions per edge, with one approach for doing so described below.

For a given frequency \(f\), let \(S_f\) be the set of nodes with frequency \(f\). All edges on paths between all pairs of nodes in \(S_f\) cannot be blockaded. Equivalently, letting \(L_f\) be the [lowest common ancestor (LCA)](https://en.wikipedia.org/wiki/Lowest_common_ancestor) of all nodes in \(S_f\), then all edges on paths between \(L_f\) and nodes in \(S_f\) cannot be blockaded. Note that the LCA of \(3\) or more nodes can be computed in terms of LCAs of pairs of nodes – for example, we can compute \(LCA(S_{f,1}, S_{f,2})\), \(LCA(S_{f,2}, S_{f,3})\), and so on, and then take the one with the minimum depth. [Tarjan's off-line LCA algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_off-line_lowest_common_ancestors_algorithm) can be used to compute all of the required LCAs in a total of \(O(N)\) time, though an online \(O(N \log(N))\) algorithm would also suffice.

Let \(D_i\) be the depth of node \(i\), and \(Z_i\) be the minimum depth of \(L_f\) for any frequency \(f\) found within \(i\)'s subtree. The edge between node \(i\) and \(P_i\) (if any) may then be blockaded if and only if \(D_i = Z_i\).

In order to compute all nodes' \(Z\) values efficiently, let's begin by computing \(L_f\) for each relevant frequency \(f\), and for each node \(i\) in \(S_f\), just setting \(Z_i\) to equal \(D_{L_f}\) (even though this may change later). Let's then recurse through the tree and process the nodes in post-order (such that each node \(i\)'s children are processed before \(i\) is processed), such that by the time we process each node \(i\), we expect \(Z_i\) to be accurate. When processing node \(i\), all we need to do is propagate its \(Z\) value up to its parent node \(P_i\), as all frequencies within \(i\)'s subtree are also within \(P_i\)'s subtree. In particular, we should update \(Z_{P_i}\) to equal \(\min(Z_{P_i}, Z_i)\).

This algorithm takes a total of as little as \(O(N)\) time.

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/0SR2rrsJLTM)