Subtask 1

Se pueden probar todas las tuplas ~(a, b, c)~ en orden lexicográfico y se añade la arista si es necesario.

Complejidad ~O(n^3)~.

Subtask 2

Ordenamos la lista de adyacencia del nodo ~x~, llamémosle ~g_x~, si solo añadimos las aristas entre ~g_{x,i}~ y ~g_{x,i+1}~ para cada ~0 \leq i < size(g_x) - 1~ al final tendremos todas las aristas que se necesitaban añadir.

Complejidad ~O(n^2)~.

Solución alternativa, que puede ser optimizada para siguientes subtareas.

Una observación crucial es que, dos nodos estarán conectados en el grafo final si hay un camino entre ellos tal que el máximo nodo de ese camino (sin contar los endpoints) es menor que ambos endpoints, esto pasa porque se puede coger el mínimo, añadir una arista entre sus dos adyacentes gracias a él, y así se reduce el camino en 1 nodo, sin cambiar el hecho de que todos los nodos del camino son menores que los endpoints.

A partir de esto se puede colorear todos los nodos de blanco, de n a 1 pintar el nodo i de negro, y contar todos los caminos que tengan endpoints negros y el resto de los nodos blancos, la complejidad es ~O(n\cdot{m})~ pero funciona rápido en la práctica.

Subtask 3

Para esta solución se requiere la observación crucial de la segunda solución de la subtarea.

Note que el grafo es un árbol, debido a esto podemos llevar un dsu, comenzando con todos los nodos blancos e ir coloreando los nodos de negro en orden ascendente; en cada componente debemos mantener ~f_i~, la cantidad de nodos blancos adyacentes a un nodo negro de la componente, al colorear el nodo ~i~ de negro, se suman todos los ~f_i~ de las componentes vecinas menos 1 a la respuesta y se actualiza ~f_i~.

Complejidad ~O(n\cdot ack(n))~.

Alternativamente se puede optimizar la primera solución de la segunda subtarea con small to large.

Subtask 4

A partir de la primera solución de la tercera subtask, podemos mantener en ~f_i~ un set con todos los nodos negros adyacentes a uno blanco de la componente, y mergear los sets con small to large, en cada paso la solución aumenta en la cantidad de elementos del set al que pertenece el nodo ~i~ después de añadir las aristas correspondientes.

Complejidad ~O(n\log^2{n})~.