Во второй почти всегда работает простой поиск базовых циклов, поэтому делаем 50 раз из рандомной вершины, мешаем ребра...:)

Третью делал ленивым апдейтом.

Вторую делал так: сделаем три итерации алгоритма — найдём произвольный цикл, попробуем обновить ответ. Затем проверим можно ли из какой-либо вершины этого цикла построить цепь, которая закончится также в одной из вершин цикла. Если такая цепь нашлась, то мы имеем 3 цикла, и после очередного обновления ответа завершим программу. Иначе если такой цепи не нашлось, значит первоначальный найденный цикл не имеет общих рёбер/вершин с каким-либо ещё циклом => мы можем удалить вершины, ему принадлежащие, из графа.

У меня стоит 75, здесь тоже полное!

Решение С за TsqrtN:

Отвечать на запрос будем таким образом: Втупую посчитаем ответ для тех которые меньше корня из n. Теперь нужно посчитать вклад тех k, которые больше корня из n, то есть сумму по всем k: n % k = n — (n / k) * k. Первое слагаемое считается очевидно, а сумму второго будем считать так, заметим, что всего корень из n различных значений n / k. Теперь заведем массив a[i] = count * i, где count — количество хедкрабов с таким i. Разделим сумму на корень из n блоков с одинаковым n / k. Для конкретного блока n / k = c, теперь нужно посчитать сумму таких k, которые деля нацело n дают частное c. Это сумма на отрезке [st, en) массива a, где st — минимальное k, такое что n / k <= c, а en минимальное k, такое что n / k < c. Утверждается, что st = n / (c + 1) + 1, но можно было искать и бинпоиском. Сумму на таком отрезке будем считать с помощью префикс сумм и sqrt-декомпозиции.

При запросах на добавление и удаление будем пересчитывать массив a, за корень из n, применяя sqrt-декомпозицию.

Также проходило решение с фенвиком вместо sqrt-декомпозиции.