How to solve Bacterial Reproduction(BACREP) from October Long 2019?

Anybody mind sharing a detailed explanation. I could only come up with the Brute Force approach during the contest.

1 Like

Check out my solution:

BACREP - “Bacterial Reproduction” - heavily-documented code; Editorial-style overview.


Thank you :slight_smile: I knew you would answer :stuck_out_tongue:

1 Like

400 lines :cold_face::cold_face:

By the way, although I would be seeing your code but from what I could think during the contest, does it have something to do with first doing an Euler Tour(ETT) over the tree and then using either a Segment Tree or Mo’s Algorithm to answer each query? I couldn’t reach to the ‘how-to’ part though, may be there is some neat trick.

Yes - Euler Tour (or DFS) plus Segment Tree is sufficient :slight_smile:


Can anybody help me what was the problem in this one ??

I was hoping 1st subtask to accept