题解 P3761 【[TJOI2017]城市】
_lgswdn
2020-05-08 13:16:11
### [$\texttt{TJOI2017-城市}$](https://www.luogu.com.cn/problem/P3761)
由于可以 $O(n^2)$，枚举每条删边。枚举删边之后对于两个树分别求出在这棵树中**距离节点 $u$ 的最远距离**，这个需要二次扫描法进行求解（即上下的树形dp）。
之后，我们要看加哪条边。显然，我们要连接两个树的“交通枢纽”然后连接。“交通枢纽”指树上到这棵树上到其他点的最远距离 最小的一个点。显然在求出最远距离后，这个也可以通过枚举求出。假设两个交通枢纽 $u,v$ 求出了，那么连接他们，最长路径即 $g_u+g_v+w$，其中 $w$ 代表
于是这个结果就是第一棵树的直径，第二棵树的直径和重新连边后的直径的最大值。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=5e3+9;
struct edge{int to,nxt,w;}e[N*2]; int hd[N],tot;
void add(int u,int v,int w){e[++tot]=(edge){v,hd[u],w};hd[u]=tot;}
int f[N][2],mx[N],g[N],tmp[2],mn[2],ans=1e9;
//f为子树里面最远的点（f[u][0]代表最远，f[u][1]代表次远），g为子树外最远的点（后面通过和f取max算出总的最远的点）
//mx记录最远的那个点是从哪个儿子节点出发的，便于后面计算g
void dfs1(int u,int fa){
for(int i=hd[u],v;i;i=e[i].nxt)
if((v=e[i].to)!=fa){
dfs1(v,u);
if(f[v][0]+e[i].w>f[u][0]){
f[u][1]=f[u][0],f[u][0]=f[v][0]+e[i].w,mx[u]=v;
}
else if(f[v][0]+e[i].w>f[u][1]) f[u][1]=f[v][0]+e[i].w;
}
}
void dfs2(int u,int fa,int k){
for(int i=hd[u],v;i;i=e[i].nxt)
if((v=e[i].to)!=fa){
if(mx[u]!=v) g[v]=max(g[u]+e[i].w,f[u][0]+e[i].w);
else g[v]=max(g[u]+e[i].w,f[u][1]+e[i].w);
dfs2(v,u,k);
}
g[u]=max(g[u],f[u][0]);
tmp[k]=max(tmp[k],g[u]);
mn[k]=min(mn[k],g[u]);
}
int main(){
int n; scanf("%d",&n);
for(int i=1,u,v,w;i<n;i++)
scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
for(int u=1;u<=n;u++){
for(int i=hd[u],v;i;i=e[i].nxt){
if((v=e[i].to)<=u) continue;
memset(f,0,sizeof(f)),memset(g,0,sizeof(g)),memset(mx,0,sizeof(mx));
tmp[0]=tmp[1]=0,mn[0]=mn[1]=1e9;
//上面是初始化
dfs1(u,v),dfs2(u,v,0),dfs1(v,u),dfs2(v,u,1);
ans=min(ans,max(max(tmp[0],tmp[1]),e[i].w+mn[0]+mn[1]));
//更新答案
}
}
printf("%d",ans);
return 0;
}
```