Go to http://agc001.contest.atcoder.jp/ and find https://gyazo.com/67c50bea10006acb6303db01a7df413f.

I was worried about the same thing. If you are logged in (see your username on the top left) and don't see a button, that means you are already registered! :)

After all there will be a center of a tree. It will be vertex or middle of an edge. Let's try all possibilities and calc distances from center to all vertices (using BFS). We have to delete all vertices with distance greater than k / 2. It is O(n²).

I had an alternative solution for C.

Let's root the tree anywhere. Define the height of the leaf as 1 and the height of the empty tree as 0. Also, since the tree has to be connected at the end, we can only remove from leaves upwards. Now calculate the following DP.

a[i][j] — the minimum number of nodes that we need to remove from the subtree i, such that the height of the tree is exactly j and the diameter of the resulting subtree will be at most K. Let s denote the son of i.

(equals to the amount of nodes in the subtree)

The idea is that if we want a height j, then we pick one deepest son, which will give us height j - 1, and then the rest of the children need to be both not deeper and not give a diameter bigger than K in combination with the deepest son. We can precompute the inside minimum as prefix array and do the whole computation efficiently.

Finally, we need to accommodate for the fact that we have picked the root randomly. This means that for any subtree we can now decide to remove the rest of the nodes, not belonging to this subtree.

Here is my code.

People already explained the smart way using tree centers.

If you're dumb like me, you can also code a DP(v, maxDepth) that tells you how many vertices you can pick in v's subtree such that the height is smaller or equal to maxDepth and diameter is smaller or equal to K. Recurrence relation is:

#case 1: biggest child depth is smaller than maxDepth-1
if maxDepth == 0: dp[v][maxDepth]=1
else: dp[v][maxDepth] = dp[v][maxDepth-1]

#case 2: biggest child depth is equal to maxDepth-1
maxAllowedDepth = min(maxDepth-1, k - 1 - maxDepth) 
s = sum (dp[child][maxAllowedDepth]) 
dp[v][maxDepth] = max (1 + dp[child][maxDepth-1] + s - dp[child][maxAllowedDepth]);

E: Since a_i, b_i are small, you can find all pairs (a_i + a_j, b_i + b_j) using a 2D FFT. Maybe also 2D Karatsuba. Then, you just need the sum of binomial coefficients over all pairs.

Yes, instead of checking for every vertex(x in editorial) we only take the center of the tree and remove the nodes which has distance more than K/2(for even). Is It Wrong?

You can add (or subtract) not just one vertex, but all vertices of the required depth in one whole subtree.

Really? My solution had just 2NC additions and didn't pass.

I believe the judger runs the code on all tests and only then reports the first failure. This is either a flaw in the system or a deliberate attempt to completely hide any information about the test number the failure was on (even if they hide the progress bar of testing, one can still say something based on the timing of the verdict).

Yes, we'll try to implement this in the future.

Yeah I think subtasks could be an interesting distinguishing feature for @coder compared to cf and tc. Having done IOI with subtasks in high school, it feels very different in a lot of open competitions where there is only AC or nothing. Of course we don't know how much they will use it in future contests but I think it has potential to make for some interesting contests.

Initially we were planning to give partial score for O(n²) in F, but it turned out that the following stupid solution passes:

while(1){
    updated = false;
    for(i=0;i<N;i++) for(j=0;j<N;j++){
        if(j minus i >= K && P[i] minus P[j] == 1){
            swap(P[i], P[j]);
            updated = true;
        }
    }
    if(!updated) break;
}

So you guys take wrong submissions as a factor of rating calculation? I found myself was 81th in the AGC001's standing but 87th in the whole rank. It's a little weird to find myself have a better rank in the standing than someone but gain less rating.

Anyway thanks for the interesting problems.:)

Well, isn't this update too aggressive? I mean, you calculated the ratings based on only one competition, but the range of rating looks quite wide. Highest is 3154 and lowest is 9. If you incrementally update this rating from now on, I'm afraid that top coders easily get strange ratings such as 6000 and you may set the ratings of many lower coders to 1.

We can take at most one node from all such values

No, we can take all nodes in any single subtree of the root. So, you can calculate the maximum of that value. (It's what I did in the contest.)