- A
- is
- the root
- the parent of B
- the left child of B
- the right child of B
- and
- B are
- siblings
- on the same level
- It is a full tree
#include <iostream>
#include <sstream>
using namespace std;
const int N = 35, M = 1010;
int postOrder[N], inOrder[M];
int l[N], r[N], fa[N], level[N], idx;
int loc[M];
bool full = true;
int build(int lp, int rp, int li, int ri, int father, int k){
if( lp>rp || li>ri ) return -1;
int u = postOrder[rp];
int t = inOrder[u];
int len = t-li;
loc[u] = idx++; //idx maybe changed in next build()
int pu = loc[u];
fa[pu] = father, level[pu] = k;
l[pu] = build(lp, lp+len-1, li, t-1, u, k+1);
r[pu] = build(lp+len, rp-1, t+1, ri, u, k+1);
if( l[pu]*r[pu]<0 ) full=false;
return u;
}
void put(bool f){
if( f ) puts("Yes");
else puts("No");
}
int main(){
int n, x, m;
scanf("%d", &n);
for( int i=0; i<n; i++ ) scanf("%d", &postOrder[i]);
for( int i=0; i<n; i++ ) scanf("%d", &x), inOrder[x]=i;
build(0, n-1, 0, n-1, -1, 0);
scanf("%d\n", &m);
string s, t;
while( m-- ){
getline(cin, s);
stringstream ssin(s);
int a, b;
if( isdigit(s[0]) ){ //A
ssin >> a >> t; //ssin >> A >> "is/and";
if( t[0]=='i' ){ //"is"
ssin >> t >> t; //ssin >> "the" >> "root/parent/left/right";
if( t[1]=='o' ) put( a==postOrder[n-1] ); //root
else if( t[1]=='a' ){ //parent
ssin >> t >> b; //ssin >> "of" >> B;
put( fa[loc[b]]==a );
}
else if( t[1]=='e' ){ //left
ssin >> t >> t >> b; //ssin >> "child" >> "of" >> B;
put( l[loc[b]]==a );
}
else{ //right
ssin >> t >> t >> b; //ssin >> "child" >> "of" >> B;
put( r[loc[b]]==a );
}
}
else{//"and"
ssin >> b >> t >> t; //ssin >> B >> "are" >> "siblings/on";
if( t[0]=='s' ) put(fa[loc[a]]==fa[loc[b]] && a!=b ); //siblings
else put( level[loc[a]]==level[loc[b]] ); //level
}
}
else put(full); //"It is a full tree"
}
return 0;
}