C++ 91pts #1WA LCA
查看原帖
C++ 91pts #1WA LCA
345930
Gold14526神金楼主2022/6/17 19:30
#include<bits/stdc++.h>
using namespace std;
int num;
char ch;
int read()
{
	num=0;
	ch=getchar();
	while(ch<'0'||ch>'9')
	{
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		num=(num<<1)+(num<<3)+ch-'0';
		ch=getchar();
	}
	return num;
}
struct tree{
	int father,l,r,high;
}t[101];
int d[101];
bool f[101];
int lca(int x,int y)
{
	memset(f,0,sizeof(0));
	f[x]=1;
	while(t[x].father)
	{
		x=t[x].father;
		f[x]=1;
	}
	while(!f[y])
	{
		y=t[y].father;
	}
	return y;
}
int main()
{
	int n=read();
	int x,y,mxh=1,mxd=1;
	t[1].high=1;
	d[1]=1;
	for(int i=1;i<n;++i)
	{
		x=read();
		y=read();
		if(t[x].l>0)
		{
			swap(t[x].l,t[x].r);
		}
		t[x].l=y;
		t[y].father=x;
		t[y].high=t[x].high+1;
		mxd=max(mxd,++d[t[y].high]);
		mxh=max(mxh,t[y].high);
	}
	x=read();
	y=read();
	int l=lca(x,y);
	printf("%d\n%d\n%d",mxh,mxd,-t[l].high*3+t[x].high*2+t[y].high);
	return 0;
}
2022/6/17 19:30
加载中...