hdu 3721 Building Roads 树的直径

题意，移动一条边，使得树的直径最小。

首先枚举拆掉的边， 拆掉边后，原图变成2颗树，然后重新连接两颗子树的某两个结点， 那么，此时答案（新树的直径）只有可能有3种情况。

1、直径完全在1子树中。

2、直径完全在2子树中。

3、直径经过了 重新建立的那条边，也就是贯穿了2颗子树。

用这3种的最大值更新ans。

求树的直径的方法可以通过dfs或者bfs,O(n)时间求出。

现在的问题在于，如何求第3种。

假设1子树存在一个点，这个点满足，任意一个点到它的距离的最大值最小。同样，2子树也找到这样一个点，然后连接这2个点，这样求得的最长链一定是最短的。

问题转化为，如何求树上的一个点，使得任意一个点到它的距离的最大值最小

假设这样一个点a不在直径上，那么它到最远距离的点，一定会和直径产生一个交点b（由直径的性质），那么a到其他点（设为x）的最大距离一定大于b到其他点（直径的端点，设为y）的最大距离。所以a一定在直径上。

证明：其实x点就是直径的端点，因为，若x不是直径的端点，那么就有ax>ay ==>bx>by==>那么y就不应该是直径的端点了。而是x。所以x一定是直径的端点。。所以ax=ab+bx，所以ax>bx。

实际上还有一个优化，就是枚举边的时候，不必枚举每一条边，只需要枚举原图的直径上的边就可以了，因为只有删掉原图的直径边，才能使直径变短。这个优化可以把时间从4800+ms降到90+ms。

题解：枚举原图直径上的边，分别求出拆掉这条边后，1,2两颗子树的直径l1,l2,再利用上述的证明求出l3

ans = min(ans,max(l1,l2,l3))；复杂度为O(n^2)

我把题目中的dfs都用一个函数写下来了，所以主函数看上去比较冗长。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<int> tree[2600];
int maps[2600][2600];
int dp[2600];
int fat[2600];
int FA[2600];
int maxn,node,ans;
void input()
{
    int a,b,c;
    scanf("%d",&n);
    for(int i=0;i<=n;i++)
    {
        tree[i].clear();
    }
    for(int i=1;i<n;i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        tree[a].push_back(b);
        tree[b].push_back(a);
        maps[a][b]=maps[b][a]=c;
    }
}
void dfs(int now,int NOT,int fa,int num=0)
{
    if(fa==-1) node=now;
    for(int i=0;i<tree[now].size();i++)
    {
        int to=tree[now][i];
        if(to!=fa&&to!=NOT)
        {
            fat[to]=now;
            dp[to]=dp[now]+maps[now][to];
            dfs(to,NOT,now);
        }
    }
    if(dp[now]>maxn)
    {
        maxn=dp[now];
        node=now;
    }
}
int main()
{
    int cas,a,b,c;
    cin>>cas;
    int ca=1;
    while(cas--)
    {
        input();
        ans=0x3f3f3f3f;
        dfs(0,-1,-1);
        int aa=node;
        dfs(aa,-1,-1);
        int bb=node;
        for(int i=0;i<n;i++) FA[i]=fat[i];
        while(bb!=aa)
        {
            int i=bb;
            int l1,l2;
            int t1=0x3f3f3f3f,t2=0x3f3f3f3f;
            maxn=0;dp[i]=0;dfs(i,FA[bb],-1);int a=node;
            maxn=0;dp[a]=0;dfs(a,FA[bb],-1);int b=node;
            l1=maxn;
            if(a==b)
            {
                l1=0;
                t1=0;
            }
            else
            {
                while(b!=a)
                {
                    t1=min(t1,max(dp[b],maxn-dp[b]));
                    b=fat[b];
                }
            }
            maxn=0;dp[FA[bb]]=0;dfs(FA[bb],i,-1);a=node;
            maxn=0;dp[a]=0;dfs(a,i,-1);b=node;
            l2=maxn;
            if(a==b)
            {
                l2=0;
                t2=0;
            }
            else
            {
                while(b!=a)
                {
                    t2=min(t2,max(dp[b],maxn-dp[b]));
                    b=fat[b];
                }
            }
            ans=min( ans, max(max(l1,l2),t1+t2+maps[i][FA[bb]]) );
            bb=FA[bb];
        }
        printf("Case %d: %d\n",ca++,ans);
    }
    return 0;
}