题目：http://codeforces.com/problemset/problem/391/E2

   题意：有三棵树。每棵树有ni个结点，加入两条边把这三棵树连接起来，合并成一棵树。使得合并的树中随意两点之间的最短路径

   的和最大。

分析：

   三棵树要合并成一棵树，则第一棵树必须选择一个点，如果为X。第二棵树必须选择两个点，如果为Y1, Y2，第三棵树必须选择一个点，如果为Z

   记第一棵树中全部结点到X的路径总和为：tot1

   第二棵树中全部结点到Y1，Y2的路径总和分别为：tot2, tot3

   第三棵树中全部结点到Z的路径总和为：tot4;

   共同拥有四种情况：

   1，每棵树内部的结点之间的距离为常数。能够求出树中一个点到剩余全部点的路径之和，把全部这种点的和相加再除以2就可以

   2，第一棵树和第二棵树这两棵树全部结点之间的距离，如果第一棵树选择结点X，第二棵树选择的左结点位Y1，

   则两棵树上随意两点a，b之间的距离。能够表示为：d(a, b) = d(a, X) + 1 + d(b, Y1),

   当中a为第一棵树的随意结点。b为第二棵树的随意结点。

   固定点a，变换bj。因为第二棵树有n2个结点，则这样的情况下的总的路径和为：(d(a, X) + 1) * n2 + sum(d(bj, Y1), j = 1, 2, ..., n2);

   再变换ai，则终于得到的路径和为：sum((d(ai, X) + 1) * n2 + sum(d(bj, Y1), j = 1, 2, ..., n2), i = 1, 2, ..., n1);

   终于结果为：sum(d(ai, X), i = 1, 2, ..., n1) * n2 + n2 * n1 + sum(d(bi, Y1), j = 1, 2, ..., n2) * n1;

   即tot1 * n2 + n2 * n1 + tot2 * n1;

   3,第二棵树和第三棵树这两棵树全部结点之间的距离，类似情况2，得到的终于结果为：tot3 * n3 + n2 * n3 + tot4 * n2;



   4，第一棵树和第三棵树全部结点之间的距离：每一条路径都能够表示为：d(a, c) = d(a, X) + 1 + d(Y1, Y2) + 1 + d(Z, c);

   终于结果为：tot1 * n3 + tot4 * n1 + n1 * n3 * d(Y1, Y2) + 2 * n1 * n3;



   综上所述，得到合并后树中结点之间的距离总和为：

   sum = (n2 + n3) * tot1 + (n1 + n2) * tot4 + n1 * n2 + n2 * n3 + 2 * n1 * n3 + n1 * tot2

    + n3 * tot3 + n1 * n3 * d(Y1, Y2) + 三棵树的内部路径;

   要使得总和最大。则tot1和tot4必须最大，上式中间部分为常数，则left = n1 * tot2 + n3 * tot3 + n1 * n3 * d(Y1, Y2)必须达到最大

   在tot2达到最大的情况下，即Y1确定时。枚举Y2使得left部分达到最大，就可以。

这过程中要枚举三棵树的位置。

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 100000 + 10;

struct Edge

{

    int y, next;

};

struct Tree

{

    LL n, head[MAXN], nodeCnt[MAXN], edgeCnt, dis[MAXN], pos, maxTot;

    LL curSum[MAXN], tot[MAXN], pathCnt;

    Edge edge[MAXN << 1];

    void addEdge(int x, int y)

    {

        edge[edgeCnt].y = y;

        edge[edgeCnt].next = head[x];

        head[x] = edgeCnt++;

    }

    void build(int n)

    {

        memset(head, -1, sizeof(head));

        this->n = n;

        int x, y;

        for(int i = 1; i < n; i++)

        {

            scanf("%d%d", &x, &y);

            addEdge(x, y);

            addEdge(y, x);

        }

    }

    /*获得son这棵树的结点数nodeCnt[son]，包含该父结点。同一时候获得son这棵树中全部子结点到son的路径之和，保存在curSum[son]

    当中curSum[son] = sum(curSum[yi] + nodeCnt[yi], i = 1, 2, ...)，即全部子树的最短路径值加上子树的全部点数的和

    */

    void dfs0(int son, int fa)

    {

        nodeCnt[son] = 1;

        curSum[son] = 0;

        int y;

        for(int i = head[son]; i != -1; i = edge[i].next)

        {

            y = edge[i].y;

            if(y == fa)

            {

                continue;

            }

            dfs0(y, son);

            //回溯。已经获得子结点y的值

            nodeCnt[son] += nodeCnt[y];

            curSum[son] += curSum[y] + nodeCnt[y];

        }

    }

    //获得tot[son]，即全部点到son的路径之和

    void dfs1(int son, int fa, LL faLeft)

    {

        //当前son所在子树的路径之和，加上其它剩余部分到son的路径之和

        tot[son] = curSum[son] + faLeft;

        int y;

        for(int i = head[son]; i != -1; i = edge[i].next)

        {

            y = edge[i].y;

            if(y == fa)

            {

                continue;

            }

            /*要算全部结点到y的最短路径之和。除了y所在子树外，应该加入的值来源有三部分：

              son这棵树原先应加上的值。即整棵大树减去son子树剩余部分到son的路径和：faLeft，

              son这棵树除了y这棵子树全部结点到son的路径值外剩余的路径和：

              son这棵树的最短路径和 - y这棵树的最短路径和 - y这棵树的结点数，即curSum[son] - curSum[y] - nodeCnt[y];

             整棵合并树减去 y子树剩余的结点数：n - nodeCnt[y]

            */

            dfs1(y, son, faLeft + curSum[son] - curSum[y] - nodeCnt[y] + n - nodeCnt[y]);

        }

    }

    //深度遍历，获得每一个结点的层次，即为到根结点的最短路径，注意根结点层次为0

    void dfs2(int son, int fa)

    {

        dis[son] = dis[fa] + 1;

        int y;

        for(int i = head[son]; i != -1; i = edge[i].next)

        {

            y = edge[i].y;

            if(y == fa)

            {

                continue;

            }

            dfs2(y, son);

        }

    }

    void solve()

    {

        dfs0(1, 0);

        dfs1(1, 0, 0);

        //求出最大的单点最短路径和，同一时候累加。即为这棵树内部的路径之和的两倍

        for(int i = 1; i <= n; i++)

        {

            pathCnt += tot[i];

            if(tot[i] > maxTot)

            {

                maxTot = tot[i];

                pos = i;

            }

        }

        dis[0] = -1;

        dfs2(pos, 0);

    }

};

Tree t[3];

LL getAns(const Tree &t1, const Tree &t2, const Tree &t3)

{

    //先算好不变的部分

    LL tmp = (t2.n + t3.n) * t1.maxTot + (t1.n + t2.n) * t3.maxTot + t1.n * t2.n + t2.n * t3.n + 2 * t1.n * t3.n

             + (t1.pathCnt + t2.pathCnt + t3.pathCnt) / 2;

    LL ans, maxAns = 0;

    //固定Y1。t2.maxTot相当于tot2

    tmp += t1.n * t2.maxTot;

    //枚举Y2

    for(int i = 1; i <= t2.n; i++)

    {

        //如果当前t2.tot[i]为tot3，t2.dis[i]为Y2到Y1的距离。Y1作为单原起点

        ans = (LL)tmp + t3.n * t2.tot[i] + t1.n * t3.n * t2.dis[i];

        maxAns = max(ans, maxAns);

    }

    return maxAns;

}

int main()

{

    int n[3], i, j;

    LL ans = 0;

    //freopen("in.txt", "r", stdin);

    scanf("%d%d%d", &n[0], &n[1], &n[2]);

    for(i = 0; i < 3; i++)

    {

        t[i].build(n[i]);

        t[i].solve();

    }

    //枚举三棵树的位置

    for(i = 0; i < 3; i++)

    {

        for(j = 0; j < 3; j++)

        {

            if(i == j)

            {

                continue;

            }

            ans = max(ans, getAns(t[i], t[j], t[3 - i - j]));

        }

    }

    printf("%I64d\n", ans);

    return 0;

}

參考博客：http://www.cnblogs.com/Delostik/p/3553114.html