Well, now that the contest is over and there are zero AKs, I feel slightly vindicated...

Edit: Sorry for the confusing comment; I think it was really badly written. I just meant that after seeing the contest results, I think the analysis in parent comment of difficulty ranging from grey to red is accurate.

We hope that all enjoyed the contest. I'd also like to apologise to those who didn't enjoy the contest, as some have told me they didn't enjoy it.

Yes. Our goal wasn't necessarily to adhere to the difficulty/format of the actual NOI as we wanted a gradient more suited to our school.

United World College Olympiad in Informatics.

https://discuss.codechef.com/t/uwcoi21e-city-mapping-2-editorial/82429
In case you missed it

I have a deterministic solution for City Mapping 2.

The idea is to use HLD to add nodes incrementally. We use $$$N$$$ queries at the start to find the root of the tree.

Now when adding a node, call it $$$x$$$, we try to find which subtree the node should go into. Let's say that currently we know the node is contained in the subtree of $$$root_c$$$, where $$$root_c=root$$$ initially. Let the node at the end of the heavy path from $$$root_c$$$ be $$$node_h$$$. There are a few cases:

• $$$lca(node_h,x)=node_h$$$. Add $$$x$$$ as a child of $$$node_h$$$.
• $$$lca(node_h,x)=x$$$. $$$x$$$ is somewhere on the path from $$$root_c$$$ to $$$node_h$$$. We can use binary lifting to find the highest parent of $$$node_h$$$ that is a descendant of $$$x$$$ (that is $$$lca(node,x)=x$$$). Then we add $$$x$$$ there.
• $$$lca(node_h,x)=w$$$ and $$$w$$$ has been found before. We set $$$root_c$$$ to the immediate child of $$$w$$$ that is a ancestor of $$$x$$$ and recurse as such. However, there is also a case where we need to make a new child of $$$node_h$$$ as $$$x$$$, so be careful of that.
• $$$lca(node_h,x)=w$$$ and $$$w$$$ has never been found before. Similar to case $$$2$$$ we use binary lifting to find the highest parent of $$$node_h$$$ that is a descendant of $$$w$$$. Then we add both $$$w$$$ and $$$x$$$ there.

Now, this part of the algorithm uses at most $$$N \log N$$$ queries on the worst case. Since $$$node_h$$$ is on the heavy child, every time we change $$$root_c$$$, the size of the search space we have to consider for $$$x$$$ at least halves. Then when we are adding $$$x$$$, we may have to do some $$$lca$$$ queries. Each $$$lca$$$ query also halves the search space.

Thus, the algorithm uses $$$N+N \log N$$$ queries total.

Code: https://www.codechef.com/viewsolution/40551263