Cotree HDU - 6567 | 树的重心

题意：
给定一个具有 n 个结点、 n−2 条边的图，保证其连通分量为 2 。现在请你添加一条边，使图连通，求连通图上任意两个结点的距离之和的最小值。

分析：
容易得出连接两个树的重心可以使得任意两点间的距离和最小。所以先求出两个树的重心，然后合并。然后再求一遍重心，目的是为了得到siz[]。然后考虑每个边的贡献：边两端点数的乘积（通过siz[]计算）
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mem(a, b) memset(a, b, sizeof(a))
#define debug(a) cout << "debug: " << a << endl;
#define fi first
#define se second
const int maxn = 1e6;
const int inf = 0x3f3f3f3f;
struct edge
{
    int ep, v, nex;
    edge(int a = 0, int b = 0, int c = 0) : ep(a), v(b), nex(c){}
}e[maxn];
int head[maxn], tot;
int n;

void addedge(int sp, int ep, int v = 1)
{
    e[tot] = edge(ep, v, head[sp]);
    head[sp] = tot++;
    e[tot] = edge(sp, v, head[ep]);
    head[ep] = tot++;
}

ll root, siz[maxn], maxp[maxn];
int vis[maxn];
ll all;

void dfs(int now, int f)//找连通分支
{
    all++;
    vis[now] = 1;
    for(int i = head[now]; ~i; i = e[i].nex)
    {
        int ep = e[i].ep;
        if(ep == f) continue;
        dfs(ep, now);
    }
}

void getroot(int now, int f)
{
    siz[now] = 1, maxp[now] = 0;
    for(int i = head[now]; ~i; i = e[i].nex)
    {
        int ep = e[i].ep;
        if(ep == f) continue;
        getroot(ep, now);
        siz[now] += siz[ep];
        maxp[now] = max(maxp[now], siz[ep]);
    }
    maxp[now] = max(maxp[now], all - siz[now]);
    if(maxp[now] < maxp[root]) root = now;
}

void init()
{
    mem(head, -1); tot = 0; mem(vis, 0);
}

int main()
{
    cin >> n;
    init();
    for(int i = 1; i <= n - 2; i++)
    {
        int x, y;
        cin >> x >> y;
        addedge(x, y);
    }
    int r1, r2;
    dfs(1, -1);
    maxp[root = 0] = all, getroot(1, -1), r1 = root;//找到第一个连通分支
    for(int i = 1; i <= n; i++) if(!vis[i]) {r2 = i; break;}
    maxp[root = 0] = (all = n - all), getroot(r2, -1), r2 = root;//找到第二个连通分支

    addedge(r1, r2);//连通
    maxp[root = 0] = all = n, getroot(r1, -1);//再调用一次求根，主要目的是求出siz
    ll res = 0;
    for(int i = 1; i <= n; i++)
        res += siz[i] * (n - siz[i]);//各条边的贡献加和
    cout << res << endl;
}