Official Editorial (C++)

Video Solution

Note: The video solution might not be the same as other solutions. Code in C++.

Explanation

Let $x$ represent the number of neighboring farms without a infected cow a farm has.

We can notice that it takes $\left \lceil{\log_2(x+1)}\right \rceil$ superspreader events for that farm to collect enough infected cows to send a infected cow to each one of its uninfected adjacent farms and keep one infected cow to itself.

Additionally, it takes an additional $x$ operations to send a cow to each one of those uninfected adjacent farms.

So, at each farm it takes $\left \lceil{\log_2(x+1)}\right \rceil + x$ operations to spread the infected cows.

Since the given graph is a tree, we can traverse through the tree, and at each farm, calculate the number of operations and add it to the answer.

Implementation 1 - BFS

Time Complexity: $\mathcal{O}(N)$

Copy
from collections import deque

# straight from stackoverflow
def ceil_log_2(x):  # returns the smallest n so that 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):

Implementation 2 - DFS

Time Complexity: $\mathcal O(N)$

Copy
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++; }