Я заметил. Но не заметил, что на двудольном, и сдал Эдмондса-Карпа. ><

Тут простая логика работала: ну не может быть в обычном срме в 500ке паросочетание в общем графе, значит граф двудольный. Я сначала сдал, а потом уже разбирался почему же он двудольный. Но я все равно потерял кучу времени, потому что сначала начал решать другую задачу: где все три стороны должны быть в массиве, но ее  я решить не смог и поэтому начал перечитывать условие.

А входить в поддерево всегда по ребру?
Я писал полагая что это всегда правильно, но у меня не проходят два теста из семплов. Вот думаю это косяк в коде или ошибка в предположении :о)

А жадность верна? Что-то я не заметил ни одного решения, кроме моего упавшего, работающего на жадности :)

Почитал едиториал - там сложнее гораздо объясняется )

А я и не заметил что мои два параметра - это остаток и результат деления на 2 твоего K, кстати по коду это заметно :)
k =k1+k2+(s1+s2)/2;
s = (s1+s2)%2;

Так сэмпл же не проходил?

еще можно так: f(n) = (n - 1) * (f(n - 1) + f(n - 2))

Включение-исключение:
C[K][0]*A[0] - C[K][1]*A[1] + C[K][2]*A[2] +C[K][3]*A[3] + ... - где A[i] - сколько вариантов таких что i фиксированных министров среди этих K получили получили свои письма, т.е. A[i] = (N-i)!
Попробуем упростить C[K][i]*A[i] = mul(i, K) * mul(K-i, N-i) где mul(a,b ) это b!/a! = (a+1)*...*b, легко выделить в отдельную функцию.

ага, более чем :)