Задача №114680. Нетреугольники
Рассмотрим неориентированный граф \(G\), каждой вершине которого сопоставлен положительный целый вес. Назовём нетреугольником в графе \(G\) тройку различных вершин \(u\), \(v\) и \(w\) такую, что хотя бы одно из рёбер \((u, v)\), \((v, w)\) или \((u, w)\) отсутствует в графе. Стоимостью нетреугольника назовём сумму весов вершин в нём. Стоимостью графа назовём максимальную стоимость нетреугольника в нём или 0, если в графе нет нетреугольников.
Дан неориентированный граф на \(n\) вершинах и последовательность из \(q\) запросов следующего вида:
- 1 u v . Добавить в граф ребро \((u, v)\) (\(1 \leq u \lt v \leq n\)). Гарантируется, что перед началом запроса ребра \((u, v)\) в графе нет.
- 2 u v . Удалить из графа ребро \((u, v)\) (\(1 \leq u \lt v \leq n\)). Гарантируется, что перед началом запроса в графе есть ребро \((u, v)\).
После каждого запроса определите стоимость получившегося графа.
В первой строке заданы три целых числа \(n, m, q\) (\(3 \leq n \leq 200\,000, 0 \leq m \leq 200\,000, 1 \leq q \leq 200\,000\)) — количество вершин в графе, количество рёбер в графе перед первым запросом и количество запросов, соответственно.
Во второй строке заданы \(n\) целых чисел \(c_i\) (\(1 \leq c_i \leq 10^8\)), \(i\)-е из которых равняется весу \(i\)-й вершины.
В следующих \(m\) строках задано описание рёбер графа перед первым запросом. В \(i\)-й из них содержится пара целых чисел \(u_i\) и \(v_i\) (\(1 \leq u_i \lt v_i \leq n\)), которая задаёт ребро между вершинами \(u_i\) и \(v_i\). Гарантируется, что каждая пара вершин \((u, v)\) встречается в списке рёбер не более одного раза.
В следующих \(q\) строках содержатся описания запросов в формате, описанном выше.
Выведите \(q\) чисел, \(i\)-е из которых равняется стоимости графа, полученного применением к нему первых \(i\) запросов.
Рассмотрим пример.
После первого запроса можно взять вершины с номерами 2, 3 и 5 (так как между вершинами 2 и 3 нет ребра) и получить стоимость графа \(2 + 3 + 5 = 10\).
После второго запроса можно взять вершины с номерами 2, 5 и 4 (так как между вершинами 2 и 5 нет ребра) и получить \(2 + 5 + 4 = 11\).
После третьего запроса можно взять вершины с номерами 3, 4 и 5 (так как между вершинами 3 и 4 нет ребра) и получить \(3 + 4 + 5 = 12\).
После четвёртого запроса можно взять вершины с номерами 2, 5 и 4 (так как между вершинами 2 и 5 нет ребра) и получить \(2 + 5 + 4 = 11\).
После пятого запроса можно взять вершины с номерами 4, 5 и 3 (так как между вершинами 4 и 5 нет ребра) и получить \(4 + 5 + 3 = 12\).
Тесты к этой задаче состоят из шести групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов необходимых групп.
| Дополнительные ограничения | |||||
| Группа | Баллы | \(n\) | \(q\) | Необх. группы | Комментарий |
| 0 | 0 | – | – | – | Тесты из условия. |
| 1 | 10 | \(n \le 10\) | \(q \le 100\) | 0 | |
| 2 | 10 | \(n \le 300\) | \(q \le 500\) | 0 – 1 | |
| 3 | 15 | \(n \le 2000\) | \(q \le 2000\) | 0 – 2 | |
| 4 | 20 | \(n \le 2000\) | – | 0 – 3 | |
| 5 | 20 | – | – | – | Нет запросов добавления. |
| 6 | 25 | – | – | 0 – 5 | |
5 4 5 1 2 3 4 5 2 5 3 5 4 5 3 4 1 2 4 2 2 5 2 3 4 1 3 4 2 4 5
10 11 12 11 12