Official Editorial (C++)

Video Solution

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

Explanation

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

We can notice that it takes ⌈log⁡2(x+1)⌉\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.

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

So, at each farm it takes ⌈log⁡2(x+1)⌉+x\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: O(N)\mathcal{O}(N)

C++

#include <bits/stdc++.h>
using namespace std;


int main() {
	int farm_num;
	cin >> farm_num;


	vector<vector<int>> neighbors(farm_num);


	// Creates a standard adjacency list

Java

import java.io.*;
import java.util.*;


public class Cowntagion {
	@SuppressWarnings("unchecked")
	// don't worry, i totally know what i'm doing
	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];

Python

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: O(N)\mathcal O(N)

C++

#include <bits/stdc++.h>


using namespace std;


#define maxn 100005


int n;
vector<int> adj[maxn];


int dfs(int start, int parent) {

Java

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

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

Join Forum