Skip to Content
CTRL K

Minimize the Diameter

Explicación

Consideremos el camino más largo que podría crear la arista agregada. Una forma de hallar este camino sería usar los dos nodos más lejanos de cada árbol respecto de los nodos que conecta la arista agregada. Por lo tanto, en cada árbol, el nodo óptimo al que conectar la arista es el que tiene el camino más corto posible hasta el nodo más lejano.

Resulta que este nodo es siempre el medio del diámetro del árbol. Para entenderlo, podemos visualizar el árbol con su diámetro como una línea horizontal, y los demás nodos “colgando” de él:

Grafo árbol con su diámetro en una línea horizontal y los demás nodos colgando hacia abajo

Nótese cómo mover el nodo a cualquier cosa que no sea 3 extiende el camino más largo por la arista que se acaba de usar.

Ahora queda calcular esta longitud resultante. Cuando la longitud del diámetro es par, el camino más largo usará la más larga de las 2 mitades del diámetro, así que hay que dividir los diámetros por 2, redondear hacia arriba y sumar 1 por la arista agregada en sí (si no se sabe cómo hallar el diámetro de un árbol, ver CPH 14.2).

Esto, sin embargo, no es necesariamente el camino más largo. Es posible que el diámetro inicial de cualquiera de los dos árboles sea más largo. Así que hay que comparar el valor de arriba también con estos.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
/** @return el nodo más lejano y su distancia desde el nodo dado. */
pair<int, int> dfs(const vector<vector<int>> &tree, int node = 1, int previous = 0,
                   int length = 0) {
	pair<int, int> max_path = {node, length};
	for (const int &i : tree[node]) {
		if (i == previous) { continue; }
		pair<int, int> other = dfs(tree, i, node, length + 1);
		if (other.second > max_path.second) { max_path = other; }
	}
	return max_path;
}
 
int main() {
	int n;
	cin >> n;
	vector<vector<int>> tree1(n + 1);
	for (int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		tree1[u].push_back(v);
		tree1[v].push_back(u);
	}
	int m;
	cin >> m;
	vector<vector<int>> tree2(m + 1);
	for (int i = 0; i < m - 1; i++) {
		int u, v;
		cin >> u >> v;
		tree2[u].push_back(v);
		tree2[v].push_back(u);
	}
 
	int tree1_start = dfs(tree1).first;
	int tree2_start = dfs(tree2).first;
	int tree1_diameter = dfs(tree1, tree1_start).second;
	int tree2_diameter = dfs(tree2, tree2_start).second;
	// (x + 1) / 2 divide por 2 y redondea hacia arriba
	int added_edge_diameter = (tree1_diameter + 1) / 2 + (tree2_diameter + 1) / 2 + 1;
 
	cout << max({tree1_diameter, tree2_diameter, added_edge_diameter}) << endl;
}
import java.io.*;
import java.util.*;
 
public class MinimizeDiameter {
	private static class Pair {
		public int first;
		public int second;
		public Pair(int first, int second) {
			this.first = first;
			this.second = second;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		List<List<Integer>> tree1 = new ArrayList<>(n + 1);
		for (int i = 0; i <= n; i++) { tree1.add(new ArrayList<>()); }
 
		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			tree1.get(u).add(v);
			tree1.get(v).add(u);
		}
 
		st = new StringTokenizer(br.readLine());
		int m = Integer.parseInt(st.nextToken());
		List<List<Integer>> tree2 = new ArrayList<>(m + 1);
		for (int i = 0; i <= m; i++) { tree2.add(new ArrayList<>()); }
 
		for (int i = 0; i < m - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			tree2.get(u).add(v);
			tree2.get(v).add(u);
		}
 
		int tree1Start = dfs(tree1).first;
		int tree2Start = dfs(tree2).first;
		int tree1Diameter = dfs(tree1, tree1Start, 0, 0).second;
		int tree2Diameter = dfs(tree2, tree2Start, 0, 0).second;
		// (x + 1) / 2 divide por 2 y redondea hacia arriba
		int addedEdgeDiameter = (tree1Diameter + 1) / 2 + (tree2Diameter + 1) / 2 + 1;
 
		int bestDiameter =
		    Math.max(Math.max(tree1Diameter, tree2Diameter), addedEdgeDiameter);
		System.out.println(bestDiameter);
	}
 
	private static Pair dfs(List<List<Integer>> tree) { return dfs(tree, 1, 0, 0); }
 
	/** @return el nodo más lejano y su distancia desde el nodo dado. */
	private static Pair dfs(List<List<Integer>> tree, int node, int previous,
	                        int length) {
		Pair maxPath = new Pair(node, length);
		for (int i : tree.get(node)) {
			if (i == previous) { continue; }
			Pair other = dfs(tree, i, node, length + 1);
			if (other.second > maxPath.second) { maxPath = other; }
		}
		return maxPath;
	}
}
Fundamentos