题解 P3019 【[USACO11MAR]会见点Meeting Place】

In_blue · 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