10367. Cowntagion

Farmer John and his fellow farmers are working tirelessly to contain the spread of the dangerous cattle disease COWVID-19 on their farms.

There are n farms under observation, numbered from 1 to n. The farms are connected by n – 1 roads, and it is possible to reach any farm from farm 1 by following some sequence of roads.

Unfortunately, a cow on farm 1 has just tested positive for COWVID-19. So far, no other cow – neither on this farm nor on any of the others – is infected. However, due to the extremely contagious nature of the disease, Farmer John realizes that on each subsequent day one of two events may occur:

· a super-spreading event occurs on some farm, doubling the number of infected cows there;

· one infected cow moves along a road from one farm to a neighboring one.

Farmer John is worried about how quickly the outbreak may spread. Help him determine the minimum possible number of days before every farm has at least one infected cow.

Input. The first line contains one integer n (1 ≤ n ≤ 10⁵). Each of the following n – 1 lines contains two integers a and b,  describing a road between farms a and b (1 ≤ a, b ≤ n).

Output. Print the minimum number of days after which the outbreak may reach every farm.

Sample input	Sample output
4 1 2 1 3 1 4	5

SOLUTION

graphs

Algorithm analysis

To infect all the farms, two types of actions must be performed:

· Movements. Exactly n − 1 cows need to be sent along the roads (each road is used at least once). Therefore, at least n − 1 days are required solely for moving the cows between farms.

· Doublings. Since initially only one cow is infected at a farm, we first need to “grow” the required number of cows by performing doubling operations.

Note that doublings and movements can occur at different locations of the tree after an infection.

Suppose one infected cow arrives at farm v. If farm v has x children in the tree, it needs to send infected cows to x neighbors, so it must have at least x cows.

Initially, farm v has 1 cow. We perform doublings: 1 → 2 → 4 → 8 …. The minimum number of doublings required to reach at least x cows is .

Thus, the minimum number of days needed to spread the disease to all farms is

(n – 1) +

According to the problem statement, it is sufficient that at some point in time at least one infected cow visits each farm. The statement does not require that after all farms are infected, each farm must still have at least one infected cow.

Algorithm implementation

The tree is stored as an adjacency list g.

vector<vector<int>> g;

The dfs function performs a depth-first search starting from vertex v and returns the number of days required to double the infected cows in all vertices of the subtree rooted at v. The parent of vertex v is par.

int dfs(int v, int par = 0)

{

int ans = 0;

for (int to : g[v])

if (to != par)

ans += dfs(to, v);

return ans + ceill(log2(g[v].size()));

}

The main part of the program. Read the input data. Build the graph.

scanf("%d", &n);

g.resize(n + 1);

for (i = 0; i < n - 1; i++)

{

scanf("%d %d", &a, &b);

g[a].push_back(b);

g[b].push_back(a);

}

Run a depth-first search starting from vertex 1 and compute the minimum number of days required to infect all farms. The result is stored in the variable res.

res = dfs(1) + n - 1;

Print the answer.

printf("%d\n", res);