萌新刚学OI1ms,样例没过求条
查看原帖
萌新刚学OI1ms,样例没过求条
941575
Stars_visitor_tyw楼主2024/7/22 20:05
#include<bits/stdc++.h>
#define int long long
#define N 200005
using namespace std;
int n, m, dep[N], dp[N][21], dis[N], x, y, dise;
vector<int> nbr[N];
bool vis[N];
void pre_lca(int cur, int fa)
{
	dis[cur]+=dis[fa];
	dp[cur][0]=fa;
	dep[cur]=dep[fa]+1;
	for(int i=1;(1<<i)<=dep[cur];i++)
	{
		dp[cur][i]=dp[dp[cur][i-1]][i-1];
	}
	for(int nxt:nbr[cur])
	{
		if(nxt!=fa)
		{
			pre_lca(nxt,cur);
		}
	}
}
int lca(int x, int y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	for(int i=20;i>=0;i--)
	{
		if(dep[x]<=dep[dp[y][i]])
		{
			y=dp[y][i];
		}
	}
	if(x==y)
	{
		return x;
	}
	for(int i=20;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i];
			y=dp[y][i];
		}
	}
	return dp[x][0];
}
void work(int x, int y)
{
	if(dep[x]>dep[y])
	{
		swap(x,y);
	}
	vis[x]=vis[y]=1;
	for(int i=20;i>=0;i--)
	{
		if(dep[x]<=dep[dp[y][i]])
		{
			y=dp[y][i];
			vis[y]=1;
		}
	}
	if(x==y)
	{
		return ;
	}
	for(int i=20;i>=0;i--)
	{
		if(dp[x][i]!=dp[y][i])
		{
			x=dp[x][i];
			y=dp[y][i];
			vis[x]=vis[y]=1;
		}
	}
//	return dp[x][0];
}
void dfs(int cur, int sum)
{
	vis[cur]=1;
	if(sum>=dise)
	{
		dise=sum;
		x=cur;
	}
	for(auto i:nbr[cur])
	{
		int nxt=i;
		if(!vis[nxt])
		{
			dfs(nxt,sum+1);
		}
	}
}
signed main()
{
	cin>>n;
	for(int i=1;i<n;i++)
	{
		int x, y;
		cin>>x>>y;
		nbr[x].push_back(y);
		nbr[y].push_back(x);
	}
	dfs(1,0);
	y=x;
	memset(vis,0,sizeof vis);
	dfs(y,0);
	swap(x,y);
	memset(vis,0,sizeof vis);
	work(x,y);
	int id, ans=0;
	for(int i=1;i<=n;i++)
	{
		int w=i;
		if(w!=x&&w!=y&&!vis[w])
		{
			int lcad=lca(w,y);
			if(ans<dise+dep[w]-dep[lcad])
			{
				id=w;
				ans=dise+dep[w]-dep[lcad];
			}
		}
	}
	cout<<ans<<"\n"<<x<<" "<<y<<" "<<id;
}
2024/7/22 20:05
加载中...