Suppose that all the keys in a binary tree are distinct positive integers. Given the postorder and inorder traversal sequences, a binary tree can be uniquely determined.

Now given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statment is one of the following:

A is the root
A and B are siblings
A is the parent of B
A is the left child of B
A is the right child of B
A and B are on the same level
It is a full tree
Note:

Two nodes are on the same level, means that they have the same depth.
A full binary tree is a tree in which every node other than the leaves has two children.

## Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary tree. The second line gives the postorder sequence and the third line gives the inorder sequence. All the numbers in a line are no more than $10^3$ and are separated by a space.

Then another positive integer M (≤30) is given, followed by M lines of statements. It is guaranteed that both A and B in the statements are in the tree.

## Output Specification:

For each statement, print in a line Yes if it is correct, or No if not.

## Sample Input:

9
16 7 11 32 28 2 23 8 15
16 23 7 32 11 2 28 15 8
7
15 is the root
8 and 2 are siblings
32 is the parent of 11
23 is the left child of 16
28 is the right child of 2
7 and 11 are on the same level
It is a full tree

Yes
No
Yes
No
Yes
Yes
Yes

## 解答

#include<iostream>
#include<unordered_map>
#include<cstring>
#include<vector>

using namespace std;

vector<int> in, post;
unordered_map<int, int> idx;
unordered_map<int, int> sibling, parent, lchild, rchild, levels;
bool isFull = true;

void build(int inl, int inr, int postl, int postr, int level) {
int mid = idx[post[postr]], leftNum = mid - inl - 1;
levels[in[mid]] = level;
int l = -1, r = -1;
if (inl <= mid - 1) {
l = post[postl + leftNum];
lchild[in[mid]] = l;
parent[l] = in[mid];
build(inl, mid - 1, postl, postl + leftNum, level + 1);
}
if (mid + 1 <= inr) {
r = post[postr - 1];
rchild[in[mid]] = r;
parent[r] = in[mid];
build(mid + 1, inr, postl + leftNum + 1, postr - 1, level + 1);
}
if (inl <= mid - 1 && mid + 1 <= inr) {
sibling[r] = l;
sibling[l] = r;
}
else if(!(inl > mid - 1 && mid + 1 > inr)){
isFull = false;
}
}

int main() {
int n, m;
scanf("%d", &n);
in.resize(n), post.resize(n);
for (int i = 0; i < n; i++) scanf("%d", &post[i]);
for (int i = 0; i < n; i++) {
scanf("%d", &in[i]);
idx[in[i]] = i;
}
build(0, n - 1, 0, n - 1, 1);
scanf("%d", &m);
int A, B;
char str, tmp, s1, s2;
for(int i = 0;i<m;i++){
scanf("%s %s ", tmp, str);
// It is a full tree
if (strcmp(tmp, "It") == 0) {
printf("%s\n", isFull ? "Yes" : "No");
scanf("%s %s %s", tmp, s1, s2);// 坑点1
}
else {
A = atoi(tmp);
if (strcmp(str, "and") == 0) {
scanf("%d %s %s", &B, s1, str);
// A and B are siblings
if (strcmp(str, "siblings") == 0)
printf("%s\n", sibling.find(A)!=sibling.end() && sibling[A] == B ? "Yes" : "No");
// A and B are on the same level
else {
printf("%s\n", levels.find(A) != levels.end() && levels.find(B) != levels.end() &&
levels[A] == levels[B] ? "Yes" : "No");
scanf("%s %s %s", s1, s2, tmp);
}
}
else {
// A is the root
scanf("%s %s", s2, str);
if (strcmp(str, "root") == 0) printf("%s\n", post[n - 1] == A ? "Yes" : "No");
else if(strcmp(str, "parent") == 0) {//A is the parent of B
scanf("%s %d", s1, &B);
printf("%s\n", parent.find(B) != parent.end() && parent[B] == A ? "Yes" : "No");
}
else if (strcmp(str, "left") == 0) {// A is the left child of B
scanf("%s %s %d", s1, s2, &B);
printf("%s\n", lchild.find(B) != lchild.end() && lchild[B] == A ? "Yes" : "No");
}
else if (strcmp(str, "right") == 0) {// A is the right child of B
scanf("%s %s %d", s1, s2, &B);
printf("%s\n", rchild.find(B) != rchild.end() && rchild[B] == A ? "Yes" : "No");
}
}
}
}
return 0;
}