Cowntagion

#include <bits/stdc++.h>
using namespace std;
 
int main() {
	int farm_num;
	cin >> farm_num;
 
	vector<vector<int>> neighbors(farm_num);
 
	// Crea una lista de adyacencia estándar
	for (int f = 0; f < farm_num - 1; f++) {
		int farm1, farm2;
		cin >> farm1 >> farm2;
		neighbors[--farm1].push_back(--farm2);
		neighbors[farm2].push_back(farm1);
	}
 
	int min_days = 0;
 
	vector<bool> visited(farm_num);
	queue<int> frontier;
	frontier.push(0);
	visited[0] = true;
 
	while (!frontier.empty()) {
		// Obtenemos la granja actual que estamos considerando y la quitamos
		// de la cola.
		int current = frontier.front();
		frontier.pop();
 
		int spread_to = 0;
		// Recorre todas las granjas vecinas que no están infectadas
		//  y las mete en la cola.
		for (int n : neighbors[current]) {
			if (!visited[n]) {
				spread_to++;
				visited[n] = true;
				frontier.push(n);
			}
		}
		// Calcula la cantidad de días superspreader necesarios y la cantidad
		//  de días para enviar esas vacas.
		min_days += ceil(log2(spread_to + 1)) + spread_to;
	}
 
	cout << min_days << endl;
}

import java.io.*;
import java.util.*;
 
public class Cowntagion {
	@SuppressWarnings("unchecked")
	// no te preocupes, sé perfectamente lo que hago
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int farmNum = Integer.parseInt(read.readLine());
		List<Integer>[] neighbors = new ArrayList[farmNum];
		for (int f = 0; f < farmNum; f++) { neighbors[f] = new ArrayList<>(); }
		for (int i = 0; i < farmNum - 1; i++) {
			StringTokenizer path = new StringTokenizer(read.readLine());
			int farm1 = Integer.parseInt(path.nextToken()) - 1;
			int farm2 = Integer.parseInt(path.nextToken()) - 1;
			neighbors[farm1].add(farm2);
			neighbors[farm2].add(farm1);
		}
 
		int minDays = 0;
		boolean[] visited = new boolean[farmNum];
		Queue<Integer> frontier = new ArrayDeque<>(Collections.singletonList(0));
		visited[0] = true;
		while (!frontier.isEmpty()) {
			int current = frontier.poll();
			// esto guarda todas las granjas a las que esta granja debería
			// esparcir para una difusión óptima
			int spreadTo = 0;
			for (int n : neighbors[current]) {
				if (!visited[n]) {
					spreadTo++;
					visited[n] = true;
					frontier.add(n);
				}
			}
			// el logaritmo en base 2 es para que haya suficientes eventos
			// superspreader para que haya suficientes vacas, y luego hay
			// que sumar la longitud de spreadTo para que las vacas
			// puedan ir realmente a las otras granjas
			minDays += ceilLog2(spreadTo + 1) + spreadTo;
		}
 
		System.out.println(minDays);
	}
 
	/** @returns el menor x tal que 2^x >= n */
	private static int ceilLog2(int n) {
		int count = 0;
		int so_far = 1;
		while (so_far < n) {
			so_far *= 2;
			count++;
		}
		return count;
	}
}

from collections import deque
 
 
# directo de stackoverflow
def ceil_log_2(x):  # devuelve el menor n tal que 2^n >= x
	return 1 if x == 0 else (x - 1).bit_length()
 
 
num_farms = int(input())
neighbors = [[] for _ in range(num_farms)]
for _ in range(num_farms - 1):
	start, end = [int(i) - 1 for i in input().split()]
	neighbors[start].append(end)
	neighbors[end].append(start)
 
min_days = 0
visited = [False for _ in range(num_farms)]
frontier = deque([0])
visited[0] = True
while frontier:
	curr = frontier.popleft()
	# spread_to guarda la cantidad de granjas vecinas a las que esta granja
	# debería esparcir para una difusión óptima
	spread_to = 0
	for n in neighbors[curr]:
		if not visited[n]:
			spread_to += 1
			visited[n] = True
			frontier.append(n)
	"""
	El logaritmo en base 2 es para que haya suficientes eventos superspreader
	para que haya suficientes vacas, y luego hay que sumar la longitud de
	spreadTo para que las vacas puedan ir realmente a las otras granjas.
	"""
	min_days += ceil_log_2(spread_to + 1) + spread_to
 
print(min_days)

#include <bits/stdc++.h>
 
using namespace std;
 
#define maxn 100005
 
int n;
vector<int> adj[maxn];
 
int dfs(int start, int parent) {
	int ans = 0;
	int cows = adj[start].size();
	if (parent == -1) {
		// el nodo padre es actualmente el nodo raíz
		cows++;
	}
 
	int curr_cows = 1;
	int days = 0;
	// contar la cantidad de eventos superspreader necesarios
	while (curr_cows < cows) {
		days++;
		curr_cows *= 2;
	}
	// enviar una vaca a cada granja adyacente sin una vaca enferma
	ans += days;
 
	for (auto next : adj[start]) {
		if (next != parent) { ans += dfs(next, start) + 1; }
	}
	return ans;
}
 
int main() {
	cin >> 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);
	}
	cout << dfs(0, -1) << endl;
	return 0;
}

import java.io.*;
import java.util.*;
 
public class Cowntagion {
	private static List<Integer>[] adj;
 
	private static int dfs(int start, int parent) {
		int ans = 0;
		int cows = adj[start].size();
		if (parent == -1) { cows++; }
 
		int currCows = 1;
		int days = 0;
		while (currCows < cows) {
			days++;
			currCows *= 2;
		}
		ans += days;
 
		for (int next : adj[start]) {
			if (next != parent) { ans += dfs(next, start) + 1; }
		}
		return ans;
	}
 
	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());
 
		adj = new ArrayList[n];
		for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); }
 
		for (int i = 0; i < n - 1; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()) - 1;
			int b = Integer.parseInt(st.nextToken()) - 1;
			adj[a].add(b);
			adj[b].add(a);
		}
 
		System.out.println(dfs(0, -1));
	}
}