The implementation of ACACIA, a new algorithm to generate dark matter halo merger trees with the Adaptive Mesh Refinement code RAMSES, is presented. The algorithm is fully parallel and based on the Message Passing Interface. As opposed to most available merger tree tools, it works on the fly during the course of the N-body simulation. It can track dark matter substructures individually using the index of the most bound particle in the clump. Once a halo (or a sub-halo) merges into another one, the algorithm still tracks it through the last identified most bound particle in the clump, allowing to check at later snapshots whether the merging event was definitive, or whether it was only temporary, with the clump only traversing another one. The same technique can be used to track orphan galaxies that are not assigned to a parent clump anymore because the clump dissolved due to numerical overmerging. We study in detail the impact of various parameters on the resulting halo catalogues and corresponding merger histories. We then compare the performance of our method using standard validation diagnostics, demonstrating that we reach a quality similar to the best available and commonly used merger tree tools. As a proof of concept, we use our merger tree algorithm together with a parametrized stellar-mass-to-halo-mass relation and generate a mock galaxy catalogue that shows good agreement with observational data.