题解：AT_abc428_e [ABC428E] Farthest Vertex

· · 题解

葬送整场比赛的题。看不懂直径的做法，来一个子树合并+换根的做法。

首先考虑处理出每一个子树 u 内深度前两大的点，要求它们分别属于子树 v_1 和 v_2 内（v_1 和 v_2 均为 u 的直接儿子，且 v_1\neq v_2）。记录它们所在的子树、它们本身的编号、距离。

定义 outmax_u（以下简称 omx_u）代表子树 u 以外的最远点距。从 fa_u 转移过来。在转移时距离要 +1。注意也要比较 fa_{fa_u} 的传递效果。这时记录两个就起到作用了，要判断自己所在的子树是否是第一大的。同样既要比距离，也要比点号大小

全程都要注意比较节点编号大小，这题我就死在 omx 没比较上。

时间复杂度 O(n)。

#include<bits/stdc++.h>
#define int long long
#define mp(a,b) make_pair(a,b)
using namespace std;

const int N=1e6+15;
vector<int> g[N];
int n;

int fa[N];
int max1[N],max1_1[N],max1_[N]; //代表第一大的
int max2[N],max2_2[N],max2_[N]; //第二大  
//分别是距离、点号、来源子树  
void dfs(int u){
    max1[u]=0,max1_1[u]=u,max1_[u]=u;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(fa[u]==v)    continue; 
        fa[v]=u;
        dfs(v);
        if(max1[v]+1>max1[u]||(max1[v]+1==max1[u]&&max1_1[v]>max1_1[u])){
            max2[u]=max1[u];
            max2_2[u]=max1_1[u],max2_[u]=max1_[u];
            max1[u]=max1[v]+1,max1_1[u]=max1_1[v],max1_[u]=v;
        }
        else if(max1[v]+1>max2[u]||(max1[v]+1==max2[u]&&max1_1[v]>max2_2[u])){
            max2[u]=max1[v]+1,max2_2[u]=max1_1[v],max2_[u]=v; 
        }
    } 
}
int omx[N]; //代表外面的最大距离 
int omx1[N];    //外面的最大点号  
void dfs2(int u){
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(fa[u]==v){
            //就要处理在 v 的情况 
//          for(int j=0;j<g[v].size();j++){
//              int v1=g[v][j];
//              if(fa[v]==v1)   continue;
//              if(v1!=u){
//                  if(max1[u])
//              }
//          } 
            if(max1_[v]==u){
                //代表是它的最大儿子 
                omx[u]=max2[v]+1;
                omx1[u]=max2_2[v]; 
            }
            else{
                omx[u]=max1[v]+1;
                omx1[u]=max1_1[v];
            }
            if(omx[v]+1>omx[u]||(omx[v]+1==omx[u]&&omx1[v]>omx1[u])){
                omx[u]=omx[v]+1;
                omx1[u]=omx1[v];
            }
        } 
    }
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        if(fa[u]==v)    continue;
        dfs2(v);
    }
}
signed main(){
    cin>>n;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    //对于最大点要维护的信息有：来源子树、点号 还有长度  
    dfs(1); 
    dfs2(1); 
    for(int i=1;i<=n;i++){
//      cout<<'#'<<i<<' '<<max1[i]<<' '<<max1_1[i]<<' '<<max1_[i]<<'|'<<max2[i]<<' '<<max2_2[i]<<' '<<max2_[i]<<'|'<<omx[i]<<' '<<omx1[i]<<endl;
        if((max1[i]>omx[i])||(max1[i]==omx[i]&&max1_1[i]>omx1[i])){
            cout<<max1_1[i]<<endl;
        }
        else cout<<omx1[i]<<endl;
    }
    cout<<endl;
}