Copied from main thread:

My solution to B — in cycle pick every city as a center.

Central city can be allocated to either top or bottom cities group depending on where you need it by shifting line some infinitesimal amount up or down. We can do it because no three cities lie on the same line.

After you picked central city you can use magic atan2 function and simulate rotating line through your central city and calculate how many people live above or below it. You can do it by sorting two lists by atan2 value (or one list) and going through it with two pointers. Pick minimum, but remember that you can always allocate central city the way it's better for you (my code was like abs(abs(x) — central)).

I bet there are easier solutions but this one got ACed and I am happy with that.

For me it was tough round, much tougher then Round 1 in GCJ this year. I solved just one problem and spend 1 hour solving Saw or Not To Saw — I think I was very close, but couldn't get through WA3 :(

I can only tell you about E as I only managed to solve this(a bit too late).

Note that there can only be at most 60 updates with k > 1, so any other update can only have k = 1. Updates with k = 1 are just like adding a node to the top of the old tree and calling this new node a root. 2 consecutive updates with k = 1 is like adding 2 nodes to the top of the tree.

So if you store updates in a queue, with all the consecutive k = 1 updates joined together then your queue length will be relatively small.

Now lets answer queries.

For every x y query I found 3 things: depth of x, depth of y and depth of lca of x and y. To do this simply travel down your queue of updates and move into the correct branch of the tree accordingly. Final answer is (depth_x-depth_lca) + (depth_y-depth_lca)

Here is my code. Hope it helps.