样例未过求调
查看原帖
样例未过求调
735763
_ChongYun_楼主2024/7/22 20:31
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct node{
	int to,nxt,val;
}w[114514<<2];
int h[114514<<2],cnt=0;
void Link(int x,int y,int val){
	++cnt;
	w[cnt].to=y;
	w[cnt].nxt=h[x];
	w[cnt].val=val;
	h[x]=cnt;
	return ;
}
int dis=-1,cur1=0,cur2=0,cur3=0;
void dfs(int op,int x,int sum,int fa){
	if(sum>=dis){
		dis=sum;
		if(!op) cur1=x;
		else cur2=x;
	}
	for(int i=h[x];i!=0;i=w[i].nxt){
		int y=w[i].to;
		if(y==fa) continue;
		dfs(op,y,sum+w[i].val,x);
	}
	return ;
}
int fa[114514<<1][25];
int dep[114514<<1];
void init_dfs(int x,int ff){
	dep[x]=dep[ff]+1;
	fa[x][0]=ff;
	for(int i=1;dep[x]>(1<<i);i++) fa[x][i]=fa[fa[x][i-1]][i-1];
	for(int i=h[x];i!=0;i=w[i].nxt){
		int y=w[i].to;
		if(y==ff) continue;
		init_dfs(y,x);
	}
	return ;
}
int lca(int x,int y){
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=30;i>=0;i--){
		if(dep[i]-(1<<i)>=dep[y]) x=fa[x][i];
	} 
	if(x==y) return x;
	for(int i=30;i>=0;i--){
		if(fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
	}
	return fa[x][0];
}
signed main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		Link(u,v,1);
		Link(v,u,1);
	}
	dfs(0,1,0,0);
	dis=-1;
	dfs(1,cur1,0,0);
	init_dfs(cur2,0);
	int ans=0;
	for(int i=1;i<=n;i++){
		if(i==cur1||i==cur2) continue;
		int qwq=lca(cur1,i);
		if(dis+dep[i]-dep[qwq]>ans){
			ans=dis+dep[i]-dep[qwq];
			cur3=i;
		}
	}
	cout<<ans<<endl;
	cout<<cur1<<" "<<cur2<<" "<<cur3<<endl;
	return 0;
} 
2024/7/22 20:31
加载中...