题解：AT_abc428_e [ABC428E] Farthest Vertex

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