题解 P3761 【[TJOI2017]城市】

\texttt{TJOI2017-城市}

由于可以 O(n^2)，枚举每条删边。枚举删边之后对于两个树分别求出在这棵树中距离节点 u 的最远距离，这个需要二次扫描法进行求解（即上下的树形dp）。

之后，我们要看加哪条边。显然，我们要连接两个树的“交通枢纽”然后连接。“交通枢纽”指树上到这棵树上到其他点的最远距离 最小的一个点。显然在求出最远距离后，这个也可以通过枚举求出。假设两个交通枢纽 u,v 求出了，那么连接他们，最长路径即 g_u+g_v+w，其中 w 代表

于是这个结果就是第一棵树的直径，第二棵树的直径和重新连边后的直径的最大值。

#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;
}