1) Notice, that after each operation we subtract n * (n + 1) / 2 in total. Thus, sum of all numbers should be divisible by this value.

2) Let k = 2 * sum / (n * (n + 1)). We'll perform exactly k operations in total.

3) Let d[i] = a[i + 1] — a[i] (differences between adjacent elements). Notice, that after each operation all of the differences decrease by 1, but one of them may (or may not if we subtract permutation 1, 2, 3 ... n) be increased by n — 1.

4) First of all, pretend that there are no operations that increase the differences — just subtract k from all of them.

Our goal is to achieve the array of differences filled with 0.

Consider some difference d[i] < 0 for some i. At some step we decreased it by 1, but we could've increase it by n — 1 instead. Thus, we may add n to it couple of times to make it 0. Please note, that we should make no more than k such operations in total. if ABS(d[i]) is not divisible by n — the answer is NO

If d[i] == 0 — we leave this value alone.

if d[i] > 0 — the answer is NO.

If everything is good in the end (we made no more than k increasing operations described above and ended up with array filled with zeroes) — the answer is YES.

The editorial has been published, but my solution differs a little bit from the one described there, so I'll try to explain it.

Let's root our tree in any non-leaf vertex (special case: n == 2)

Consider the vertex v such as all of it's children are leaves with values a[0] ... a[k]. We have 2 options for paths containing these leaves:

1) Pair these leaves with each other (paths of the first type)

2) Pair these leaves with some other leaves in some other sub-tree. (paths of the second type)

Consider we decided to have exactly c path of the first type. The thing is that we can calculate the exact value of c.

Let sum = a[0] + a[1] + ... + a[k].

Then a[v] = c + (sum — 2c) = sum — c (We'll subtract c from a[v] when we'll use the paths of the first type; please note, that after that we'll have to use exactly sum — 2c paths of the second type)

c = sum — a[v].

But, there are 2 limitations on c:

1) it has to be non-negative

2) We should be able to actually create c paths of the first type.

To check the second condition calculate the maximum achievable number of paths of the first type. Let max = MAX(a[0],a[1]...a[k]). It's easy to see, that if (2*max <= sum) then maxC = sum / 2; else maxC = sum — max.

If these conditions do not hold — the answer is NO.

Now we can consider the vertex v as a leaf with value (sum — 2c) and solve the problem recursively.

If everything was OK for all of the vertices and (sum — 2c) == 0 for the root — the answer is YES, otherwise the answer is NO

Editorial (English version starts from the page 4)

My explanation of that solution

Starting from some rating (I don't actually know treshold) you can choose color if you want to.