COWVID-19 Spread Optimization

Farmer John and his dedicated team are working round the clock to curb the spread of COWVID-19 across his farms. There are N farms numbered from 1 to N, and these farms are connected by N − 1 roads in such a way that one can reach any farm from farm 1.

Initially, only farm 1 has exactly one infected cow, while all other farms are disease‐free. However, due to the disease’s highly contagious nature, Farmer John believes that on each day one of the following events will occur:

1. At any single farm, a super‐spreader event doubles the number of infected cows there (i.e. if there were x cows, the new number becomes 2x).
2. An infected cow moves from one farm to an adjacent farm (along a road). Note that if a cow moves from a farm, that farm loses one infected cow. To keep that farm still infected (i.e. with at least one cow remaining), the farm must have at least 2 infected cows before the move.

The goal is to plan a sequence of daily events so that eventually every farm has at least one infected cow. In other words, find the minimum number of days required so that all farms become infected.

Observation: We can view the farms as vertices in a tree rooted at 1. For each farm, suppose it must send infected cows to m child farms. In order to send m moves (each move sending one cow to a child) while retaining one infected cow locally, the farm must first have at least m + 1 infected cows. Since doubling a farm’s current count multiplies it by 2, if we start with 1 infected cow, then by doing k doubling events the count becomes 2^k. Thus, we require the smallest integer k satisfying

[ 2^{k} \geq m+1 ]

for each farm that needs to transmit the infection. In addition, each edge in the tree represents exactly one cow move. Therefore, the minimum total number of days is the sum of all moves (which is N − 1) and the doubling events required over all farms.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 10⁵), the number of farms. Each of the following N − 1 lines contains two integers u and v (1 ≤ u, v ≤ N), indicating that there is a road connecting farm u and farm v.

outputFormat

Output a single integer — the minimum number of days required to ensure that every farm has at least one infected cow.

sample

1

0