Skip to Content
CTRL K

Village (Minimum)

Análisis oficial 

Explicación

Este problema se puede resolver con un enfoque voraz (greedy). En particular, hacemos una búsqueda en profundidad (DFS) sobre el árbol dado. Para cada nodo (aldeano) que sigue en su posición original, lo intercambiamos con su único vecino, es decir, su nodo padre. Para el nodo raíz, que no tiene padre, podemos intercambiarlo con cualquiera de sus hijos.

Al intercambiar dos nodos de los cuales al menos uno aún no está procesado, podemos garantizar que ningún nodo volverá a su posición original. También podemos mostrar que intercambiar entre vecinos es la solución óptima: supongamos que intercambiamos dos nodos no procesados que no son vecinos. La distancia que los dos nodos necesitan recorrer sería entonces mayor o igual que 4. Si en cambio solo los intercambiamos con sus respectivos vecinos, la distancia que necesitan recorrer es exactamente 4. Por lo tanto, intercambiar nodos que no son vecinos nunca lleva a una mejor solución.

Para ilustrar esta idea, consideremos el siguiente ejemplo:

Example 1

Los nodos 2 y 3 aún no se intercambiaron. Ahora, si intercambiamos los nodos 2 y 3 de forma directa, la distancia total recorrida sería 2∗2=42 * 2 = 4. Nunca será menor que simplemente intercambiar los nodos con sus vecinos, que en este caso significa intercambiar el nodo 1 con 2 y luego el nodo 2 con 3, lo que da una distancia total de 2∗(2∗1)=42 * (2 * 1) = 4.

Si hay más nodos entre el nodo 2 y el 3, entonces la distancia necesaria para intercambiarlos de forma directa será mayor que 4. En el siguiente grafo, la distancia total recorrida sería 2∗3=62 * 3 = 6, mientras que la distancia de solo intercambiar nodos con sus vecinos se mantiene igual, es decir, 4.

Example 2

Implementación

Complejidad temporal: O(N)\mathcal{O}(N)

#include <bits/stdc++.h>
using namespace std;
 
/**
 * Perform a depth-first search on the given node and swap villagers if
 * necessary.
 * @return the sum of distances villagers need to travel
 */
int dfs(int node, int parent, vector<int> &changed_to, const vector<vector<int>> &adj) {
	int length_added = 0;
 
	for (int &child : adj[node]) {
		if (child == parent) { continue; }
		length_added += dfs(child, node, changed_to, adj);
	}
 
	/*
	 * If the current node (villager) is still in its original house, exchange
	 * its position with its parent node.
	 */
	if (parent >= 0 && changed_to[node] == node) {
		changed_to[node] = changed_to[parent];
		changed_to[parent] = node;
		length_added += 2;
	} else if (parent < 0 && changed_to[node] == node) {
		/*
		 * If the current node is the root and did not swap its position yet,
		 * swap it with any of its children.
		 */
		changed_to[node] = changed_to[adj[node][0]];
		changed_to[adj[node][0]] = node;
		length_added += 2;
	}
 
	return length_added;
}
 
int main() {
	int N;
	cin >> N;
 
	/*
	 * Villager i will move to house changed_to[i]. At the beginning, all
	 * villagers are in their own house, i.e. changed_to[i] = i
	 */
	vector<int> changed_to(N);
	vector<vector<int>> adj(N);
	for (int i = 0; i < N - 1; i++) {
		int a, b;
		cin >> a >> b;
		a--, b--;
		adj[a].push_back(b);
		adj[b].push_back(a);
		changed_to[i] = i;
	}
	changed_to[N - 1] = N - 1;
 
	int total_length = dfs(0, -1, changed_to, adj);
 
	cout << total_length << endl;
	for (int &i : changed_to) { cout << i + 1 << " "; }
	cout << endl;
}
Fundamentos