Auto comment: topic has been updated by drexdelta1 (previous revision, new revision, compare).

Keeping the set of people on the current path in a set<int> or similar structure will have a time complexity, which is unlikely to pass. In a set it is for inserting, deleting and finding the minimal a elements. However you insert and delete more often than you find the minimal elements.

There exists a data structure which lets you insert and delete elements in , while taking to find the minimal elements. For this, divide the range of legal values into equal blocks and for each block keep a hash table containing all the added elements in that block. To insert or delete, simply access the relevant hash table, to find minimal, iterate through all possible elements while skipping the ranges where the hash table is empty. Using this, the complexity is

It is also worth noting that in the case of this problem, after you flatten the tree into an array, instead of dividing into blocks of cities, you should divide into blocks of people, otherwise Mo's algorithm won't optimize as intended.

This is still quite slow, the constant is large and hash-tables only support on average, not every time. I would prefer to use a method that uses time. Centroid decomposition works really well here, HLD is not bad either.