divide by zero subtrees problem


can anybody explain idea to solve this problem

Let’s assume that K >= 1, e.g. there is at least one vertex which we must choose.

The basic idea is that there’s some minimal subtree T which contains all K points and whose leaves are some of the K points. We can find it by sequentially removing leaves that are not among the K points; that can be done in O(N) using a BFS (starting from the removed leaves of the original tree), where we keep one vector listing the degrees of all nodes in the tree left so far.

Now, we can take the original tree, pick one of the K points to be the root, and count for every vertex V using a tree DP, in how many ways we can choose its (rooted) subtree which includes V. It can be counted easily - if you know the answers for its sons ans[son[i]], then for every son[i], you can choose not to add that son (or any vertex in its subtree, then), or add it (giving ans[son[i]] ways to do it), and those decisions are independent among different sons, so ans[V]=product(ans[son[i]]+1), and ans[V]=1 for a leaf, which has no sons.

How does this help? Consider vertices U and V; U is in the subtree T (above) and V is not. Then we have (independently on those choices for all other pairs (U,V)) ans[V]+1 ways to pick the subtree of V - empty or one of the ans[V] non-empty ones. It’s really the right value, because the original tree is split into a subtree of V, which contains only some vertices not in T, and a subtree of U, which contains all other vertices, and therefore also the root; we’re choosing either “the resulting subtrees which don’t contain any vertices from the subtree of V” or “which contain V and vertices corresponding to one of ans[V] ways that hold connectivity in the subtree of V”.

We still need the case K=0. Just pick any vertex as the root, do the same tree DP and sum up the ans[i] for all vertices - every subtree (the ones that we’re supposed to count) now has a unique root, and we just count all of them over all those roots.

The algorithm for K >= 1 is now clear: find the vertices belonging to the minimal subtree T; root at one of the K points, do the tree DP to find the ways to pick a subtree rooted at each V; try all edges, if it connects a vertex U from T and a vertex V not from T, multiply the result by ans[V]+1. Time: O(N).

1 Like

here is what i understood please correct me if i am wrong
first calculate minimum subtree containing all locations using a dfs
then start dp calculation from one of the locations
if the child vertex is in minimal tree then include it else multiply by dp[child]+1 (i.e we can include that child and any of its subtree vertices or not)

Else just if the parent vertex of that child is in the min. tree. Aside from that, yes.