PTA 家谱处理

这题一开始以为是大模拟，但是看了别人以后的题解发现，有更好的解法。
我们可以观察出，这个输入顺序决定了每个人的num-2个空格一定是他的父亲，所以直接记录就行，lca暴力跳就可以了，不用倍增。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
#include<cmath>
#include<map> 
#include<string>
#include<queue>
#include<stack> 
#include<bitset>
#include<list>
#include<set>
#include<utility>
#include<functional>
#include<iomanip>
#define IO ios::sync_with_stdio(false)
#define eps 1e-7
#define int long long
using namespace std;
const string last="null";
map<int,string>mp1;
map<string,string>mp2;
int n,m;
string test;
signed main()
{
	cin>>n>>m;
	getchar();
	//mp1[0]=last;
	for(int i=1;i<=n;i++)
	{
		string s;
		getline(cin,s);
		int num=0;//count(s.begin(),s.end(),' ');
		for(int j=0;j<s.size();j++)
		{
			if(s[j]==' ')num++;
		}
		//cout<<s<<" 123: "<<num<<endl;
		string ss=s.substr(num);
		if(num==0)
		{
			mp2[s]=last;
			mp1[num]=s;
		}
		else
		{
			mp1[num]=ss;
			mp2[ss]=mp1[num-2];
		}
	}
	/*while(cin>>test)
	{
		cout<<"zuxian: "<<test<<" "<<mp2[test]<<endl;
	}*/
	for(int i=1;i<=m;i++)
	{
		string a,b,c,d;
		cin>>a>>d>>d>>b>>d>>c;
		if(b[0]=='c')
		{
			if(mp2[a]==c)
			{
				cout<<"True"<<endl;
			}
			else
			{
				cout<<"False"<<endl;
			}
		}
		else if(b[0]=='a')
		{
			string ss=c;
			//cout<<ss<<" "<<mp2[ss]<<endl;
			while(mp2[ss]!=a&&mp2[ss]!=last)
			{
				//cout<<"123:: "<<ss<<endl;
				ss=mp2[ss];
			}
			//cout<<ss<<endl;
			if(mp2[ss]!=last)
			{
				cout<<"True"<<endl;
			}
			else
			{
				cout<<"False"<<endl;
			}
		}
		else if(b[0]=='s')
		{
			if(mp2[a]==mp2[c])
			{
				cout<<"True"<<endl;
			}
			else
			{
				cout<<"False"<<endl;
			}
		}
		else if(b[0]=='d')
		{
			string ss=a;
			//cout<<ss<<" "<<mp2[ss]<<endl;
			while(mp2[ss]!=c&&mp2[ss]!=last)
			{
				//cout<<"123:: "<<ss<<endl;
				ss=mp2[ss];
			}
			//cout<<ss<<endl;
			if(mp2[ss]!=last)
			{
				cout<<"True"<<endl;
			}
			else
			{
				cout<<"False"<<endl;
			}
		}
		else if(b[0]=='p')
		{
			if(mp2[c]==a)
			{
				cout<<"True"<<endl;
			}
			else
			{
				cout<<"False"<<endl;
			}
		}
	}
}