P3761 [TJOI2017]城市

注意到两个城市之间的最大交通费用就是树的直径。

考虑枚举删去哪一条边，假设删的是边 $u,v$ ，那么我们发现直径可能有三种选择：

$1.$ 直径缩在蓝色子树里面。

$2.$ 直径缩在红色子树里面。

上面两种情况，我们都不能通过加边来缩短直径，是无法掌控的。

$3.$ 直径的一段在蓝色子树里面，另一端在红色子树里面，这时直径必定跨越边 $u,v$

如图所示，黄色部分代表直径。

注意图中的 $u,v$ 是你新增的边的端点。

于是问题转化为在蓝色子树和红色子树里面选两个点 $p,q$ ，并且连边，使得蓝色子树里面的点到 $p$ 的距离最大值+ $u,v$ 边权+红色子树里面的点到 $q$ 的距离的最大值最小。

不妨将这样的点称为树的中心，将树的中心和树上每一个点之间距离的最大值称为树的半径。

感性理解一下，树的中心一定在直径上面。

如何证明呢？

考虑把整棵树表示为直径上面连着一大堆子树的形式。

假设我们现在选择了某个子树里面的点 $u$ ，设 $v$ 是这个子树的根的父亲，考虑证明 $v$ 是更优的选择。

把距离 $u$ 最远的点记为 $w$ 。

$1.w$ 不属于这个子树： $dis(u,w)=dis(u,v)+dis(v,w)>dis(v,w)$ ，显然选择 $v$ 最优。

$2.w$ 属于这个子树：

慢慢证明：

首先，树上距离 $v$ 最远的点一定是 $p$ 或 $q$ 。

否则假设距离 $v$ 最远的点是 $r$ ，那么 $p-v-r$ 或者 $r-v-q$ 这条路径肯定比 $p-v-q$ 长， $p-q$ 就不是直径了。

由于对称性，不妨设距离 $v$ 最远的点是 $p$ 。

我们有 $dis(u,w)>dis(u,v)+dis(v,p)$

考虑设 $u-w,u-v$ 路径的最上面一个交点为 $O$ 。

注意到 $dis(u,w)=dis(u,O)+dis(O,w)$ 。

且 $dis(u,p)=dis(u,O)+dis(O,v)+dis(v,p)$ 。

那么 $dis(u,p)<dis(u,w) \to dis(O,v)+dis(v,p)<dis(O,w)$ 。

而显然 $dis(v,p)>dis(v,O)+dis(O,w)$ （由于我们刚才的假设）

那么 $dis(O,v)+dis(v,p)>dis(O,w)+dis(O,v) \times 2$ 。

和上面的式子矛盾。

所以 $w$ 肯定不属于这个子树。

所以，我们找出蓝色部分和红色部分的子树，枚举直径上面每个点，计算这个点和直径两个端点的距离即可。

时间复杂度 $O(n^2)$

代码：

#include <bits/stdc++.h>
#define MAXN 5005
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^'0');
        ch=getchar();
    }
    return x*f;
}
struct Edge{
    int to,len;
};
vector<Edge>G[MAXN];
inline void AddEdge(int u,int v,int w){
    G[u].push_back(Edge{v,w});
}
int n;
int fa[MAXN],d[MAXN];
int vis[MAXN];
queue<int>Q;
inline int bfs(int u,int father){
    while (Q.size()) Q.pop();
    memset(vis,0,sizeof(vis));
    memset(fa,0,sizeof(fa));
    memset(d,0,sizeof(d));
    fa[u]=father,d[u]=0;
    vis[u]=vis[father]=1;//等于是阻断到另一个子树的路
    Q.push(u);
    int ans=0;
    while (Q.size()){
        int u=Q.front();Q.pop();
        vis[u]=true;
        if (d[u]>d[ans]) ans=u;
        for (register int i=0;i<G[u].size();++i){
            int v=G[u][i].to,w=G[u][i].len;
            if (vis[v]) continue;
            d[v]=d[u]+w;
            fa[v]=u;//记录父亲，等于是记录直径
            Q.push(v);
        }
    }
    return ans;
}
inline int FindMid(int p,int q){//树的半径的长度，q为最深的点
    int len=d[q];
    int ans=0x7fffffff;
    while (true){
        ans=min(ans,max(d[q],len-d[q]));
        q=fa[q];//慢慢爬上来
        if (q==0) break;
    }
    return ans;
}
int U[MAXN],V[MAXN],W[MAXN];
int main(){
    int n=read();
    for (register int i=1;i<n;++i){
        U[i]=read(),V[i]=read(),W[i]=read();
        AddEdge(U[i],V[i],W[i]);
        AddEdge(V[i],U[i],W[i]);
    }
    int ans=0x7fffffff;
    for (register int i=1;i<n;++i){
        int u=U[i],v=V[i];
        
        int p1=bfs(u,v);int q1=bfs(p1,v);//直径的两个端点
        int len1=d[q1];int ans1=FindMid(p1,q1);

        int p2=bfs(v,u);int q2=bfs(p2,u);
        int len2=d[q2];int ans2=FindMid(p2,q2);

        ans=min(ans,max(max(len1,len2),ans1+W[i]+ans2));
    }
    printf("%d\n",ans);
}

总结：

在此题中我们大量使用反证法，通过构造新的直径和更长的长度来证明结论。