Yes I saw that this doesn't work, but assume that you always pass the minimum distance (-1 if none exists) to a police station in your subtrees to your parent when you moving up the dfs tree. Now you only cut edges if the distances has exceeded d. So in your case we would have cut (1,2) when coming back from 2 to 1. And we cut as well if we arrive at a police station moving back up and some police station is present in the subtree.

What is a counterexample to the greedy solution of D? I don't understand why this doesn't work.

As it took me ages to figure out the recurrence for DIV1.C. I hope this will clarify things for others. Somebody already mentioned above that the problem can be reduced to a non-decreasing sequence by considering the sequence a_i - i. From now on we will just consider a_i = a_i - i.

The second thing that one can prove is that there always exists an optimal solution, where one a_i is not changed. Hint: Just consider an optimal solution where this does not hold.

Let b_i be the sorted sequence of a_i. Let dp_i, j be the optimal value for the prefix a₁... a_i while ending in a value smaller or equal to b_j. The recurrence is then as follows

dp_i, j = min{ dp_{i, j - 1},  dp_{i - 1, j} +  |b_j - a_i| }

Why? Either we let the prefix a₁... a_i end in a value smaller then b_j - 1 ( hence also smaller then b_j) or we let the prefix a₁... a_i - 1 end in a value smaller or equal to b_j and also let a_i be equal to b_j. There are some base cases and this can of course be adapted for linear space.

Edit: 20669994

Could someone explain this testcase (which is the 37th) of Problem E?

10 10 1 10
1 5 178
1 8 221
2 7 92
2 8 159
3 5 55
3 6 179
3 10 237
4 8 205
5 6 191
8 10 157

The output is NO for all edges except the two that lie on the unique shortest path of length 378, for which the answer is YES. What I don't understand is why the answer for all other edges is NO. Let's take for example the path (1 — 5 — 3 — 10 ) of length 470. The first and the last edge could be reduced by 93 to give a path of length 377 in which case they lie on the unique shortest path. I probably misunderstood something in the problem statement. Thanks in advance.

Just two that came to mind are: convex hull and sweep line

I understood everything up to the point you explain. But then the author does some jump which I am unable to follow, mainly how the same sum can be expressed differently in terms of b_i's where b_i is a good number.

So what exacly am I supposed to compute in terms of b_i's for a given a_i and why is the transformation from the inclusion-exclusion formula to the b_i formula correct?

I feel like this editorial anwser is the perfect example where one has to dicipher half the anwser.

Would you mind to elaborate a bit more? It's not clear to me.

It works because you integrate the topsort in Kosaraju's algorithm. In general a topsort only works on DAG's. If somebody would implement Kosaraju and Topsort seperatly it might fail, maybe you should mention that in the write-up. Otherwise nice tutorial.