自动搬运

查看原文

来自洛谷，原作者为

	In_blue **

搬运于2025-08-24 21:44:27，当前版本为作者最后更新于2019-09-27 19:37:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

看了很久的题解，发现大佬们的代码十分深奥，看都看不懂QWQ

进入正题

看都这题，首先就看数据范围

数据好水

于是就有了一个暴力枚举的思想:

1.题目说这是一个树形结构，所以理想当然的的想到了用数组模拟建树。我们定义a[i]保存的为父节点的位置，x为父节点的位置；于是就有了a[i]=x；
2.题目意思是让我们找出x，y的最近父节点，那么我们可以开两个bool数组bol1[],bol2[]，分别保存x的各个父节点和y的各个父节点，并使x，y相继保存它们的父节点。这是我们可以发现，当第一次x的父节点中有y时或是y的父节点中有x时，就是答案。即（bol1[y]==1||bol2[x]==1)时，输出为真的点即可；

以下是代码

#include<iostream>
#include<cstring>
using namespace std;
int a[1010];
int x,y;
int m,n;
int main()
{
	cin>>n>>m;
	for(int i=2;i<=n;i++)
	{
		cin>>x;
		a[i]=x;
	}
	for(int i=1;i<=m;i++)
	{
		cin>>x>>y;
		bool bol1[1010],bol2[1010];
		memset(bol1,0,sizeof(bol1));
		memset(bol2,0,sizeof(bol2));
		bol1[x]=1;
		bol2[y]=1;
		bool t=0;
		if(x!=y)
		{
			while(a[x] && a[y])
			{
				x=a[x];
				y=a[y];
				bol1[x]=1;
				bol2[y]=1;
				if(bol1[y]||bol2[x])
				{
					t=1;
					if(bol1[y])
					{
						cout<<y<<endl;
						break;
					}
					cout<<x<<endl;
					break;
				}
			}
		}
		else cout<<x<<endl,t=1;
		if(t==0)cout<<1<<endl;
	}
	return 0;
}

警告：不要抄代码！！！！

求过QAQ