Author: Trung Nguyen
Tester and Editorialist: Alei Reyes ## Problem Link
Practice
Difficulty
Medium
PREREQUISITES:
Bruteforce, Tree and DFS
Problem
Given a tree with vertices labelled from 1 to N, we want to find a connected subgraph S that maximizes |S|*AND(S).
Explanation
The strategy is to fix the AND, and find the maximum size of a connected subgraph with that given AND.
Suppose that the AND of some set S is A. Since we are dealing with bitwise operations, it is useful to see the binary representation of A.
If A has a bit turned on in position i, then all the elements of S should have also bit i turned on. Similarly if A has a bit turned off in position i, then there should be at least one element in S with a bit turned off in position i.
That means that all elements of S are supermasks of A i.e they can be generated by turning on some of the bits of A.
To find the largest set S with AND(S) = A, we can paint all the vertices that are supermask of A, and find the maximum connected component that has all its vertices painted.
We’ll paint the vertices that are supermasks of A one by one (in any order), and we’ll keep the connected components in a disjoint set union data structure (dsu).
After rooting the tree in one of its vertices, we get an orientation of the edges, this will be important to keep the connected components. Let p[u] be the parent of u in the tree.
Let’s suppose we are painting node u, it is possible that its parent p[u] is also a supermask of A. In this case we have to update the dsu by merging the components of u and p[u].
Once we have painted all the supermasks of A, the dsu can tell us the component of maximum size.
What is the complexity of our algorithm? We are iterating over all the supermasks of every A from 1 to N. Let’s suppose that A has b bits (for the problem b is at most 17). Then a mask that has k bits turned off will have 2k supermasks. Therefore the number of operations is ∑0 ≤ k ≤ b binomial(b, k) · 2k = 3b (by the binomial theorem)