Backup Cable#13117
There are cities in a country, connected by n-1 two-way roads. There is exactly one simple path between any two cities.
To make the road network more reliable, exactly one new road will be built between two distinct cities that are not already connected directly.
After construction, consider n-1 independent failure scenarios. In scenario , only the -th original road becomes unavailable. All other roads, including the new road, remain available. The network is restored before each scenario.
The damage caused by a failure is the number of cities outside the largest connected component after the corresponding road is removed. If all cities remain connected, the damage is zero.
Choose the new road to minimize the sum of damages over all n-1 scenarios. Find this minimum sum.
The first line contains an integer (3\le n\le 2\cdot10^5) — the number of cities.
Each of the next n-1 lines contains two integers u_i,v_i (1\le u_i,v_i\le n, u_i\ne v_i) — the endpoints of the -th original road.
The original road network is guaranteed to be a tree.
Print one integer — the minimum possible sum of damages after building one new road.
Beispiel 1
Beispiel 2
Beispiel 3
In the first example, build a road between cities and . A failure of any original road then leaves the network connected, so the answer is .
In the second example, build a road between cities and . Failures of roads and do not disconnect the network. A failure of road isolates one city. The total damage is .
In the third example, the new road can protect only two original roads. Each of the other two failures isolates one city, so the answer is .
Subtask ( points): n\le 9.
Subtask ( points): n\le 100.
Subtask ( points): n\le 2000.
Subtask ( points): at most one city is directly connected by original roads to more than two other cities.
Subtask ( points): no additional constraints.