这是
Cotree
Problem Description
Avin has two trees which are not connected. He asks you to add an edge between them to make them connected while minimizing the function $\sum_{i=1}^{n} \sum_{j=i+1}^{n} dis(i,j)$ , where $dis(i,j)$ represents the number of edges of the path from $i$ to $j$. He is happy with only the function value.
Input
The first line contains a number $n (2 \leq n \leq 100000)$.In each of the following $n−2$ lines, there are two numbers $u$ and $v$ , meaning that there is an edge between $u$ and $v$. The input is guaranteed to contain exactly two trees.
Output
Just print the minimum function value.
Sample Input
3
1 2
Sample Output
4
solution
题目大意是保证给你两棵树，将他们用一条边连接，使得两棵树变成一棵树，使得 function $\sum_{i=1}^{n} \sum_{j=i+1}^{n} dis(i,j)$最小，并求出最小值。（两结点的距离即 i -> j 路径上边的数量）