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 (Sigma_{i = 1}^nSigma_{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<=n<=100000). In each of the following n−2lines, 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
首先dfs求连通块确定出这些点分属于哪棵树，然后两次dfs求出来两棵树的重心（求中心大概也是可的），把重心连起来就得到了最后的树。剩下要做的就是统计任意两点之间的距离和。直接遍历点显然会T（也会有重复），不妨统计边的贡献，再开一个sz数组计算新树的各个子树的size，再来一次dfs直接计算累加答案即可。
#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n, m, tot = 0, head[N], ver[2 * N], Next[2 * N];
bool belong[N];//表示i这个点属于哪棵树 默认初始化为0
int tree_size[2] = { 0 };
//求树的重心
int size[N], // 这个节点的“大小”（所有子树上节点数 + 该节点）
weight[N], // 这个节点的“重量”
centroid[2]; // 用于记录树的重心（存的是节点编号）
int minn;
void add(int x, int y) {
ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void getBelong(int x, int pre) {
belong[x] = 1;//
tree_size[1]++;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre || belong[y]) continue;
getBelong(y, x);
}
}
void GetCentroid(int x, int pre) {
size[x] = 1;
weight[x] = 0;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
GetCentroid(y, x);
size[x] += size[y];
//weight[x] = max(weight[x], weight[y]);
weight[x] = max(weight[x], size[y]);
}
weight[x] = max(weight[x], tree_size[belong[x]] - size[x]);//注意这里不要误写成n - size[x]
if(weight[x] <= minn) {
minn = weight[x];
centroid[belong[x]] = x;
}
}
long long ans = 0;
int sz[N];
void calc(int x, int pre) {
sz[x] = 1;
for(int i = head[x]; i; i = Next[i]) {
int y = ver[i];
if(y == pre) continue;
calc(y, x);
ans += 1ll * sz[y] * (n - sz[y]);//计算贡献
sz[x] += sz[y];
}
}
int main() {
cin >> n;
memset(belong, 0, sizeof(belong));
for(int i = 1; i <= n - 2; i++) {
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
}
getBelong(1, 0);//把和第一个点联通的设置为1 其他的自然为0
tree_size[0] = n - tree_size[1];
minn = 0x3f3f3f3f;
GetCentroid(1, -1);
minn = 0x3f3f3f3f;
for(int i = 1; i <= n; i++) {
if(belong[i] != belong[1]) {
GetCentroid(i, -1);
break;
}
}
add(centroid[0], centroid[1]);
add(centroid[1], centroid[0]);
//cout << centroid[1] << ' ' << centroid[0] << endl;
//剩下的就是求树上点两两之间的距离和了
calc(1, 0);
cout << ans << endl;
return 0;
}