模拟
#include <iostream>
#include <cstring>
#include <vector>
#define r() fast_read()
#define f(inc, frm, to) for (size_t inc = frm; inc < to; ++inc)
using namespace std;
const int N = 3E1 + 5E0;
inline int fast_read(void) {
int n = 0, sign = 1;
char c = getchar();
while (c < 48 or c > 57) {
if (c == '-') sign = ~0;
c = getchar();
}
while (c >= 48 and c <= 57) {
n = (n << 1) + (n << 3) + (c ^ 48);
c = getchar();
}
return sign * n;
}
static std::vector<std::string> split(const std::string& str, const std::string& delimiter) {
char* save = nullptr;
char* token = strtok_r(const_cast<char*>(str.c_str()), delimiter.c_str(), &save);
std::vector<std::string> result;
while (token != nullptr)
{
result.emplace_back(token);
token = strtok_r(nullptr, delimiter.c_str(), &save);
}
return result;
}
struct TNode {
int l_child;
int r_child;
int parent;
int level;
} nodes[1001];
int n, m, a, b;
int post[N], in[N];
inline int build(int i, int j, int n, int d) {
if (n <= 0) return 0; // 空子树
const int root = *(post + i + n - 1);
nodes[root].level = d;
if (n == 1) return root; // 叶节点
int k = j;
while (*(in + k) != root) ++k;
int l = k - j;
nodes[root].l_child = build(i, j, l, d + 1);
nodes[root].r_child = build(i + l, k + 1, n - 1 - l, d + 1);
nodes[nodes[root].l_child].parent = nodes[nodes[root].r_child].parent = root;
return root;
}
inline void test_sample(void) {
f(i, 0, 31)
printf("%ld: %d %d %d %d\n",
i, nodes[i].l_child, nodes[i].r_child, nodes[i].parent, nodes[i].level);
}
signed main(int argc, char const *argv[]) {
// freopen("test.in", "r", stdin);
n = r();
f(i, 0, n) *(post + i) = r();
f(i, 0, n) *(in + i) = r();
build(0, 0, n, 1);
// test_sample();
m = r();
string s;
while (m--) {
getline(cin, s);
vector<string> strs = split(s, " ");
if (s.find("root") != string::npos) {
a = stoi(strs.front());
// 没有双亲节点的节点称做 root 节点
puts(not nodes[a].parent ? "Yes" : "No");
} else if (s.find("siblings") != string::npos) {
a = stoi(strs.front()), b = stoi(strs[2]);
// a 和 b 的双亲节点是同一节点, a 和 b 互为兄弟关系
puts(nodes[a].parent == nodes[b].parent ? "Yes" : "No");
} else if (s.find("parent") != string::npos) {
a = stoi(strs.front()), b = stoi(strs.back());
puts(nodes[b].parent == a ? "Yes" : "No");
} else if (s.find("left") != string::npos) {
a = stoi(strs.front()), b = stoi(strs.back());
puts(nodes[b].l_child == a ? "Yes" : "No");
} else if (s.find("right") != string::npos) {
a = stoi(strs.front()), b = stoi(strs.back());
puts(nodes[b].r_child == a ? "Yes" : "No");
} else if (s.find("level") != string::npos) {
a = stoi(strs.front()), b = stoi(strs[2]);
puts(nodes[a].level == nodes[b].level ? "Yes" : "No");
} else {
bool flag = 1;
int node;
f(i, 0, n) {
node = post[i];
if ((nodes[node].l_child and nodes[node].r_child == 0) or
(nodes[node].r_child and nodes[node].l_child == 0)) {
flag = 0; break;
}
}
puts(flag ? "Yes" : "No");
}
}
// fclose(stdin);
return ~~(0 ^ 0);
}
求关注