从加里敦大学城市规划专业毕业的小明来到了一个地区城市规划局工作。这个地区一共有\(n\)座城市，\(n-1\)条高速公路，保证了任意两运城市之间都可以通过高速公路相互可达，但是通过一条高速公路需要收取一定的交通费用。小明对这个地区深入研究后，觉得这个地区的交通费用太贵。
小明想彻底改造这个地区，但是由于上司给他的资源有限，因而小明现在只能对一条高速公路进行改造，改造的方式就是去掉一条高速公路，并且重新修建一条一样的高速公路(即交通费用一样），使得这个地区的两个城市之间的最大交通费用最小（即使得交通费用最大的两座城市之间的交通费用最小），并且保证修建完之后任意两座城市相互可达。如果你是小明，你怎么解决这个问题？
对于\(100\%\)的数据，\(1<=n<=5000，1 <= u,v <= n，1<= d <= 2000\)
这恰好也是国庆第三天考试的时候的最后一道题。
首先我们要是对这颗树改造之后的直径最小，那么我们选择改造的这条边一定在直径上，因为如果不在直径上，那么无论如何改造其他的边，最长的路径都不会改变。
我们枚举直径上的所有边，暴力改造。
我们再去掉这条边之后，会把这棵树分为两个部分，那么在拼接之后得到的这棵新树，它的直径可能有三种情况：
\(1.\)两个端点都在连通块\(1\)中
\(2.\)两个端点都在连通块\(2\)中
\(3.\)一个端点在连通块\(1\)，一个端点在连通块\(2\)。
前两种情况很明显求一下直径即可。
对于第三种情况，我们实际上就是要在连通块一中选一个点\(u\)，以及在连通块二中选一个点\(v\)，使得\(u/v\)在连通块一\(/\)二中到任意一点的最长距离最小（事实上这也正是半径，注：半径并不等于直径的一半）。
用到了换根\(DP\)。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=5010;
int head[maxn],tot;
struct Edge
{
int from,to,nxt,w;
Edge(){};
Edge(int from,int to,int nxt,int w):from(from),to(to),nxt(nxt),w(w){};
}ed[maxn<<1];
void add(int u,int v,int w)
{
ed[++tot]=Edge(u,v,head[u],w);
head[u]=tot;
ed[++tot]=Edge(v,u,head[v],w);
head[v]=tot;
}
int f[maxn][2];//f[u][0]表示u的子树以它为一个端点的距离最长的链的长度,f[u][1]表示次长
int son[maxn];//son[u]表示直径中经过的那个儿子
int g[maxn];//g[u]表示u的子树外到u的最长距离
int vis[maxn];
template<class T>void read(T &x)
{
bool f=0;char ch=getchar();x=0;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
if(f) x=-x;
}
int r1,r2;
void dfs(int u,int &dis)
{
vis[u]=1;
for(int i=head[u];i;i=ed[i].nxt)
{
int v=ed[i].to;
if(vis[v]) continue;
dfs(v,dis);
dis=max(dis,f[v][0]+f[u][0]+ed[i].w);
if(f[v][0]+ed[i].w>f[u][0])
f[u][1]=f[u][0],f[u][0]=f[v][0]+ed[i].w,son[u]=v;//虽然可能有几个儿子都是直径
//经过的（因为直径可能有多条），但是因为他们的最长链都是一样的，所以并不影响
else if(f[v][0]+ed[i].w>f[u][1]) f[u][1]=f[v][0]+ed[i].w;
}
}
void rdfs(int u,int tag)
{
if(!tag) r1=min(r1,max(f[u][0],g[u]));
else r2=min(r2,max(f[u][0],g[u]));
vis[u]=1;
for(int i=head[u];i;i=ed[i].nxt)
{
int v=ed[i].to;
if(vis[v]) continue;
if(v==son[u]) g[v]=max(g[u]+ed[i].w,f[u][1]+ed[i].w);//如果只有这一个儿子经过直
//径，那么这个正确性是显然的，而若有两个至多个，因为只有其中的一个被标记为了经过直径的儿子，
//所以其他的是可以把这个答案给更新的
else g[v]=max(g[u]+ed[i].w,f[u][0]+ed[i].w);
rdfs(v,tag);
}
}
void init()
{
memset(g,0,sizeof(g));
memset(f,0,sizeof(f));
memset(vis,0,sizeof(vis));
}
int main()
{
int n;
read(n);
for(int i=1;i<=n-1;++i)
{
int u,v,w;
read(u);read(v);read(w);
add(u,v,w);
}
int ans=0x7fffffff;
for(int i=1;i<=tot;i+=2)
{
init();
int u=ed[i].from,v=ed[i].to;
int dis1=0,dis2=0;
vis[u]=vis[v]=1;
dfs(u,dis1);dfs(v,dis2);memset(vis,0,sizeof(vis));
r1=0x7fffffff,r2=0x7fffffff;
vis[u]=vis[v]=1;
rdfs(u,0);rdfs(v,1);
ans=min(ans,max(dis1,max(dis2,r1+r2+ed[i].w)));
}
printf("%d\n",ans);
return 0;
}原文：https://www.cnblogs.com/iwillenter-top1/p/11861980.html