思路:
1.是否性别相同很好判断,主要是判断关系是否出了五服。
2.建图:孩子指向双亲。
3.判断小于等于五代内二者是否有公共祖先。
判断小于等于五代内二者是否有公共祖先:
1.对两人分别做一次dfs。
2.五代关系便是边界,超了五代就返回。
3.标记第一人五代内所有祖先,然后第二人开搜。
4.如果第二人搜的过程中存在被标记过的人,说明未超五服,终是兄妹。
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
typedef long long LL;
const int N = 1e5 + 10;
// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;
// const int P = 1 << 10;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<LL, int> PLI;
typedef pair<int, string> PIS;
typedef pair<double, int> PDI;
typedef pair<string, int> PSI;
const double eps = 1e-4;
const int mod = 1e9 + 7;
int n, k;
int m;
int Q;
// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int h[N];
int e[M];
int ne[M];
int idx;
int gender[N];
int depth[N];
int fa[N][21];
int din[N];
bool st[N];
bool flag;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs(int u, int num)
{
if (num >= 4)
{
return;
}
st[u] = true;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (!st[j])
{
st[j] = true;
dfs(j, num + 1);
}
else
{
flag = true;
return;
}
}
}
void solve()
{
scanf("%d", &n);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
{
int id, fid, mid;
char c;
scanf("%d %c %d %d", &id, &c, &fid, &mid);
st[id] = true;
if (c == 'M')
{
gender[id] = 1;
}
else
{
gender[id] = 2;
}
if (fid != -1)
{
add(id, fid);
gender[fid] = 1;
}
if (mid != -1)
{
add(id, mid);
gender[mid] = 2;
}
}
scanf("%d", &m);
while (m--)
{
int a, b;
scanf("%d %d", &a, &b);
if (gender[a] == gender[b])
{
puts("Never Mind");
}
else
{
memset(st, 0, sizeof st);
st[a] = true;
st[b] = true;
flag = 0;x
dfs(a, 0);
dfs(b, 0);
if (!flag)
{
puts("Yes");
}
else
{
puts("No");
}
}
}
}
int main()
{
int t = 1;
// init(1000000);
// scanf("%d", &t);
// getchar();
while (t--)
{
// cout << (2563 % 11) << endl;
// cout << t << endl;
solve();
// cout << '\0' << endl;
// cout << f(4);
// cout<<(25 >> 5)
// cout << gcd(31415, 14142);//
// cout << (28284 / 11) << endl;
}
return 0;
}
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/