Skip to Content
CTRL K

Journey

Solución oficial (C++) 

Explicación

El primer paso es calcular la longitud y la probabilidad de cada camino posible. Podemos hacerlo con DFS. Empezamos con una probabilidad de 1, o 100%. Luego, para cada nodo, dividimos la probabilidad del camino actual por la cantidad de siguientes movimientos posibles.

Por ejemplo, si el nodo 1 está conectado a los nodos 2 y 3, la probabilidad de llegar al nodo 2 es 12\frac{1}{2}, o 0.50.5, y la probabilidad de llegar al nodo 3 es también 0.50.5. Si el nodo 3 está conectado a los nodos 4 y 5, la probabilidad de llegar al nodo 4 es 0.5÷2=0.250.5 \div 2 = 0.25 y la probabilidad de llegar al nodo 5 es también 0.250.25. Digamos que los nodos 2, 4 y 5 son hojas. Los caminos posibles se listan abajo:

  • 1→21 \rightarrow 2 : 0.50.5
  • 1→3→41 \rightarrow 3 \rightarrow 4 : 0.250.25
  • 1→3→51 \rightarrow 3 \rightarrow 5 : 0.250.25

Para calcular la longitud esperada del viaje, multiplicamos cada una de las probabilidades por la longitud de camino correspondiente. En el ejemplo de arriba, la longitud esperada sería 1⋅0.5+2⋅0.25+2⋅0.25=1.51\cdot0.5 + 2\cdot0.25 + 2\cdot0.25 = 1.5

En el código, para cada nodo, calculamos la cantidad de siguientes movimientos posibles recorriendo los vecinos del nodo y contando cuántos no están visitados. Si no hay tales nodos, el camino terminó y podemos sumar la longitud del camino por la probabilidad a la respuesta final. Si no, dividimos la probabilidad (como se describió arriba) y continuamos el DFS.

Nota: setprecision(10) fija en 10 la cantidad de decimales a imprimir. Ver esto  para más detalles.

Implementación

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

#include <bits/stdc++.h>
using namespace std;
 
int n;
vector<vector<int>> adj;  // lista de adyacencia
vector<bool> visited;     // guarda qué nodos fueron visitados
 
double ans;
 
void dfs(int node, int current_length, double current_probability) {
	visited[node] = true;
	int possible_moves = 0;
	// contamos la cantidad de ciudades a las que podemos movernos
	for (int x : adj[node]) {
		if (!visited[x]) { possible_moves++; }
	}
 
	if (!possible_moves) {
		// si no hay ciudades a las que movernos, el camino terminó
		ans += current_length * current_probability;
	} else {
		// actualizamos la nueva probabilidad dividiéndola
		// por la cantidad de ciudades posibles
		double new_probability = current_probability / possible_moves;
		for (int x : adj[node]) {
			if (!visited[x]) { dfs(x, current_length + 1, new_probability); }
		}
	}
}
 
int main() {
	cin >> n;
	adj.resize(n + 1);
	visited.resize(n + 1);
 
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		adj[a].push_back(b);
		adj[b].push_back(a);
	}
 
	// el recorrido empieza en el nodo 1, longitud de camino 0 y probabilidad 100%.
	dfs(1, 0, 1);
 
	cout << setprecision(10) << ans << endl;
}
import java.util.*;
 
public class Journey {
	public static double ans = 0;
	public static Map<Integer, List<Integer>> adjList;  // lista de adyacencia
	public static boolean[] visited;  // guarda qué nodos fueron visitados
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		adjList = new HashMap<>();
 
		for (int i = 0; i <= n; i++) { adjList.put(i, new ArrayList<>()); }
		for (int i = 1; i < n; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			adjList.get(a).add(b);
			adjList.get(b).add(a);
		}
 
		visited = new boolean[n + 1];
 
		// el recorrido empieza en el nodo 1, longitud de camino 0
		// y probabilidad 100%.
		dfs(1, 0, 1.0);
 
		System.out.println(String.format("%.10f", ans));
	}
 
	public static void dfs(int node, int current_length, double current_probability) {
		visited[node] = true;
 
		int possible_moves = 0;
		// contamos la cantidad de ciudades a las que podemos movernos
		for (int x : adjList.get(node)) {
			if (!visited[x]) { possible_moves++; }
		}
 
		if (possible_moves == 0) {
			// si no hay ciudades a las que movernos, el camino terminó
			ans += current_length * current_probability;
		} else {
			// actualizamos la nueva probabilidad dividiéndola
			// por la cantidad de ciudades posibles
			double new_probability = current_probability / possible_moves;
			for (int x : adjList.get(node)) {
				if (!visited[x]) { dfs(x, current_length + 1, new_probability); }
			}
		}
	}
}
class Point:
	"""Representa un punto o nodo a lo largo de la frontera de nuestro recorrido DFS."""
 
	def __init__(self, node: int, length: int, probability: float):
		self.node = node
		self.length = length
		self.probability = probability
 
 
n = int(input())
graph = [[] for _ in range(n)]
 
for _ in range(n - 1):
	a, b = map(lambda i: int(i) - 1, input().split())
	graph[a].append(b)
	graph[b].append(a)
 
visited = [False] * n
visited[0] = True
stack = [Point(0, 0, 1)]
 
end_lengths = []
while stack:
	curr = stack.pop()
 
	possible_moves = 0
	for adj in graph[curr.node]:
		if not visited[adj]:
			possible_moves += 1
 
	for adj in graph[curr.node]:
		if not visited[adj]:
			stack.append(Point(adj, curr.length + 1, curr.probability / possible_moves))
			visited[adj] = True
 
	if not possible_moves:  # el nodo actual es el final de un camino
		end_lengths.append((curr.length, curr.probability))
 
expected_value = 0
for length, probability in end_lengths:
	expected_value += length * probability
print(expected_value)
Fundamentos