CO92TREE - EDITORIAL

Author: Trung Nguyen
Tester and Editorialist: Alei Reyes ## Problem Link
Practice

Contest

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)

Implementation

Author’s Solution

Tester’s and Editorialist’s Solution

2 Likes

When a child v of u, is a supermask of A(Here we are visiting u after v). Then, why are we not merging u and v components?

Also, linking with parents is more time efficient as there can be at most one parent…can’t say that about the no. of children.

Why am I getting TLE ??

This is the link of my code.

https://www.codechef.com/viewsolution/17936474

Thank you in advance.

eventually we’ll visit both vertices. When we visit the child, the edge to its parent will be added.

1 Like

Yeah! Got it.