Steven_Meng's Blog

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)$

所以$dis(u,w)>-dis(u,v)+dis(v,p)$

移项，得：$dis(u,w)+dis(u,v)>dis(v,p)$

同时加上$dis(v,q)$

$dis(u,w)+dis(u,v)+dis(v,q)>dis(v,p)+dis(v,q)$

于是$q-v-u-w$这条路径可以成为更优的直径，造成矛盾。

所以$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);
}