update 2020/7/15 优化了一下 markdown 的用法，增加了前面的题目描述。

题目：

题目描述

从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有 n 座城市，n-1 条高速公路，保证了任意两运城市之间都可以通过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明对这个地区深入研究后，觉得这个地区的交通费用太贵。

小明想彻底改造这个地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路（即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任意两座城市相互可达。如果你是小明，你怎么解决这个问题？

输入格式

输入数据的第一行为一个整数 n，代表城市个数。

接下来的 n - 1 行分别代表了最初的 n - 1 条公路情况。每一行都有三个整数 u,v,d 。u,v 代表这条公路的两端城市标号，d 代表这条公路的交通费用。

1 \leq u,v \leq ， 1\leq d \leq 2000 。

输出格式

输出数据仅有一行，一个整数，表示进行了最优的改造之后，该地区两城市 之间最大交通费用。

首先由 n \leq 5000 ,时间限制是 3s 我们可以确定本题 O(n^2)可以卡过去。

初步解法

我们就可以先有一个 O(n^2) 的暴力解法。 （这一版基本是照着某一楼的题解打出来的） 我们枚举每一条边断开，然后求连个联通块各自的直径，以及两个联通块的最短半径，基本可以说是半个纯暴力。

void Diameter(const int u)//找直径的函数
{   
    book[u] = 1;//用来标记是否遍历过。

    for(reg int i = head[u]; i ; i = e[i].next)
        if(!book[e[i].to])
        {
            Diameter(e[i].to);

            int v = f[e[i].to][0] + e[i].wi;

            if(v > f[u][0]){f[u][1] = f[u][0];f[u][0] = v;mv[u] = e[i].to;}

            else if(v > f[u][1]){f[u][1] = v;}
        }
    diameter = Max(diameter,f[u][1] + f[u][0]);//很标准的一个求树直径的 DP。
}

void Radius(const int u,const int front)//找半径的函数
{   // front 用来记录自身子树内的最短半径。
    book[u] = 0;radius = Min(radius,Max(front,f[u][0]));

    for(reg int i = head[u]; i ; i = e[i].next)
        if(book[e[i].to]) Radius(e[i].to,Max(front,mv[u] == e[i].to ? f[u][1] : f[u][0]) + e[i].wi);
}

int main()
{
    n = Read();

    for(reg int i = 1; i < n ; ++i) add_edge(Read(),Read(),Read());

    for(reg int i = 2; i <= tot_edge; i += 2)
    {
        int d1,d2,r1,r2;

        diameter = 0;

        book[e[i].to]=1;

        Diameter(e[i^1].to);

        d1 = diameter;

        diameter = 0;

        Diameter(e[i].to);

        d2 = diameter;

        book[e[i^1].to]=0;

        radius = INF;

        Radius(e[i].to,0);

        r1 = radius;

        radius = INF;

        Radius(e[i^1].to,0);

        r2 = radius;

        Ans = Min(Ans,Max(Max(d1,d2),r1+r2+e[i].wi));

        for(reg int i = 1 ; i <= n; ++i) {f[i][0] = mv[i] = f[i][1] = book[i] = 0;}
    }

    printf("%d",Ans);

    return 0;
}

如何优化？

优化一：断边

断的边一定在原来树的直径上，且是树所有直径的公共边。

对于非直径上的边，就算断掉，剩下的两个联通块的直径有一个还是原来的直径，所以对其我们要求的答案无影响。

然后直径的非公共边。 如图树的直径有两条， 1->8 和 1->9 ，断掉 5->6,5->7,6->9,7->8 中的任意一条，都不会让剩下的两个联通块的直径减小，所以其对答案也无影响。 （这里的性质使选原树任意一条直径进行删边都可以找到正确答案所删的那一条边）

由此我们可以得到一个优化， 时间复杂度是 O(nL) , L 是原树直径的边数。

void dfs(const int u,const int fa)
{   
    for(reg int i = head[u]; i ; i = e[i].next)
        if(e[i].to != fa)
        {
            dis[e[i].to] = dis[u] + e[i].wi;

            mv[e[i].to] = i;

            dfs(e[i].to,u);
        }
}

void Diameter(const int u)
{   
    book[u] = 1;

    for(reg int i = head[u]; i ; i = e[i].next)
        if(!book[e[i].to])
        {
            Diameter(e[i].to);

            int v = f[e[i].to][0] + e[i].wi;

            if(v > f[u][0]){f[u][1] = f[u][0];f[u][0] = v;mv[u] = e[i].to;}

            else if(v > f[u][1]){f[u][1] = v;}
        }
    diameter = Max(diameter,f[u][1] + f[u][0]);
}

void Radius(const int u,const int front)
{   
    book[u] = 0;radius = Min(radius,Max(front,f[u][0]));

    for(reg int i = head[u]; i ; i = e[i].next)
        if(book[e[i].to]) Radius(e[i].to,Max(front,mv[u] == e[i].to ? f[u][1] : f[u][0]) + e[i].wi);
}

int main()
{
    n = Read();

    for(reg int i = 1; i < n ; ++i) add_edge(Read(),Read(),Read());

    dfs(1,1);

    for(reg int i = 1; i <= n ; ++i) if(dis[S] < dis[i]) S = i;

    dis[S] = 0;

    for(reg int i = 1; i <= n ; ++i) mv[i] = 0;

    dfs(S,S);

    for(reg int i = 1; i <= n ; ++i) if(dis[T] < dis[i]) T = i;

    for(reg int i = mv[T]; i ; i = mv[e[i^1].to])  
        ded[++tde] = i;

    for(reg int i = 1; i <= n ; ++i) mv[i] = 0;

    for(reg int i = 1; i <= tde; i++)//可优化，只删直径 
    {
        int d1,d2,r1,r2;

        diameter = 0;

        book[e[ded[i]].to]=1;

        Diameter(e[ded[i]^1].to);

        d1 = diameter;

        diameter = 0;

        Diameter(e[ded[i]].to);

        d2 = diameter;

        book[e[ded[i]^1].to]=0;

        radius = INF;

        Radius(e[ded[i]].to,0);

        r1 = radius;

        radius = INF;

        Radius(e[ded[i]^1].to,0);

        r2 = radius;

        Ans = Min(Ans,Max(Max(d1,d2),r1+r2+e[ded[i]].wi));

        for(reg int i = 1 ; i <= n; ++i) {f[i][0] = mv[i] = f[i][1] = book[i] = 0;}
    }

    printf("%d",Ans);

    return 0;
}

优化效果：

从 17.55s -> 1.61s ,挂了氧气能达到 871ms 。

O(n^2)

O(nL)

氧气

优化二：连边

$2.$ 如果连的不是直径上的点，那么可以确定新树的直径是两个联通块直径上的较长链相加在加上连接点到各自直径的距离，是一定长于 方案 $1$ 的。 所以可以写一个找直径中点的函数代替上文中找半径的函数。 这个函数时间复杂度很难算，姑且可当做 $\Omega(1)$ ，卡一卡就变 $O（L）$ 了。 可以证明的是联通块上的直径一定有一半以上的长度是与原树直径重合的（只需要理解一下上文用 $DP$ 求直径的做法)，可以用这个性质来找中点。 ~~这个优化代码我没单独写~~ ``` int rt=0,lt=0,Half = ans>>1,cur; cur = i; while(dp[cur][0] - WW[cur] > Half && cur) cur = mvv[cur]; rt = dp[cur][0]; cur = mv[i]; Half = (f[mv[i]][0] + f[mv[i]][1])>>1; while(f[cur][0] - W[cur]> Half && cur) cur = mv[cur]; lt = f[cur][0]; ans = Max(ans,W[i] + lt + rt); ``` ## 终极优化 ~~调了很久也没调出来。~~ 我们在直径上遍历删边的时候，不难发现做了很多的重复的遍历。  ### 黄色是断了的边。 ### 对于断边左侧：从上往下的过程中，红色的点进行了多余的遍历，只有橙色的点才是需要遍历的。 ### 对于断边右侧：我们发现若是从最左边的点进行第一次遍历，那么我们便已经得到了右联通块需要的所有信息。 在找右边直径的过程都是可以通过 $O(n)$ 预处理变成 $O(1)$ 的。 在找左边直径的过程可以用 $book$ 数组标记，不重复遍历，也可以实现整体 $O(n)$的。 最终加上连边的优化是可以达到 $\Omega(n)$？ 需要特别注意的是，会有特殊的数据如图：  就是如图所示，删去 $6 -> 1$ 的边后最长链不经过 $1$ 点，这需要特殊处理。 即断的边的端点不一定在断边后联通块的直径上。 我的想法就是先找到最长链的两个端点，再分别从两个端点跑一次 $dfs$ 。 要记录两个东西。 当前子树直径。 据当前子树根节点最近的直径上的节点。 ``` void dfs1(const int u,const int fa) { for(reg int i = head[u]; i ; i = e[i].next) if(e[i].to != fa) { dfs1(e[i].to,u); int v = f[e[i].to][0] + e[i].wi; if(v > f[u][0]){f[u][1] = f[u][0];f[u][0] = v;mv[u] = e[i].to;W[u] = e[i].wi;} else if(v > f[u][1]){f[u][1] = v;} A[u] = Max(A[u],A[e[i].to]); } A[u] = Max(A[u],f[u][1] + f[u][0]); } void dfs(const int u,const int fa) { for(reg int i = head[u]; i ; i = e[i].next) if(e[i].to != fa) { dfs(e[i].to,u); int v = dp[e[i].to][0] + e[i].wi; if(v > dp[u][0]){dp[u][1] = dp[u][0];dp[u][0] = v;mvv[u] = e[i].to;WW[u] = e[i].wi;} else if(v > dp[u][1]){dp[u][1] = v;} B[u] = Max(B[u],B[e[i].to]); } B[u] = Max(B[u],dp[u][1] + dp[u][0]); } ``` #### 记录每一个子树的最长链，次长链，然后断的边移动，但是不用 $DP$ 了，可以直接从数组中找到当前情况下各联通块的直径，最后找一下对应直径中点就可以找到答案了。