团体程序设计天梯赛-练习集 - L3-016 二叉搜索树的结构 （30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
structnode{
intd;
node*left, *right;
};
unordered_map<int,int>lvl;
unordered_map<int,node*>fu;
node*insertBST(node*rt,intd,intl,node*fa)
{
if(rt==NULL)
    {
rt=newnode;
rt->left=rt->right=NULL;
rt->d=d;
lvl[d]=l;
if(fa==NULL) fa=rt;
fu[d]=fa;
returnrt;
    }
if(rt->d>d) rt->left=insertBST(rt->left,d,l+1,rt);
elseif(rt->d<d) rt->right=insertBST(rt->right,d,l+1,rt);
}
intmain()
{
intn,a,q,b;
stringts;
scanf("%d",&n);
node*tree=NULL;
for(inti=0;i<n;i++)
scanf("%d",&a),
tree=insertBST(tree,a,1,tree);
scanf("%d",&q);
while(q--)
    {
intf=0,flag=0;
cin>>a>>ts;
if(lvl[a]==0) flag=1;
if(ts[0]=='i')
        {
cin>>ts>>ts;
if(ts[1]=='o')
            {
if(!flag&&fu[a]->d==a) f=1;
            }
elseif(ts[0]=='p')
            {
cin>>ts>>b;
if(lvl[b]==0) flag=1;
if(!flag&&fu[b]->d==a&&a!=b) f=1;
            }
elseif(ts[0]=='l')
            {
cin>>ts>>ts>>b;
if(lvl[b]==0) flag=1;
if(!flag&&fu[a]->d!=a)
                {
node*l=fu[a]->left;
if(!flag&&l!=NULL&&l->d==a&&fu[a]->d==b) f=1;
                }
            }
elseif(ts[1]=='i')
            {
cin>>ts>>ts>>b;
if(lvl[b]==0) flag=1;
if(!flag&&fu[a]->d!=a)
                {
node*r=fu[a]->right;
if(!flag&&r!=NULL&&r->d==a&&fu[a]->d==b) f=1;
                }
            }
        }
else        {
cin>>b;
getline(cin,ts);
if(lvl[b]==0) flag=1;
if(ts[ts.length()-1]=='s')
            {
if(!flag&&fu[a]==fu[b]) f=1;
            }
else            {
if(!flag&&lvl[a]==lvl[b]) f=1;
            }
        }
if(flag==1) f=0;
puts(f?"Yes":"No");
    }
return0;
}