非常折磨的维京人

思路

• 理解题意最重要
• 这里定义的五代之内和之前愿天下有情人都是失散多年的兄妹这题的五代之内不太一样，本题要求如过A的10代祖先和B的3代祖先相同，那也不能结婚。
• 假设A、B的共同祖先为C，那么对A来说C是五代之外的祖先，对B来说C五代之外的祖先，同时满足才说明A和B五代之内没有共同祖先。这主要是因为题目没有说给出的两个人是同辈关系。

注意

• 对于非维京人祖先的处理，可以都相同，但是要特判。或者直接处理为他们的祖先都不同，这样就不同特判了
• 当枚举A、B两个人的祖先都超过五代的时候，直接结束，他俩一定可以结婚，否则会超时
• 记录祖先的时候用代数映射祖先姓名，这样遍历才能保证第一次的相同的祖先是最近的

#include <bits/stdc++.h>
#define int long long
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int N = 1e5 + 10, M = N * 2;
const int INF = 0x3f3f3f3f3f3f3f3f;
map<string, string> dad;
map<string, int> is_wei;
map<string, int> sex;
// 记录name的祖先
void up(string name, int d, map<int, string>& fa)
{ 
    if(name == "")  return ;
    fa[d] = name;
    d += 1;
    up(dad[name], d, fa);
}
signed main()
{
     int n;
     cin >> n;
     for(int i = 0; i < n; i ++)
     {
         string name, xing;
         cin >> name >> xing;
         int len = xing.size();
         if(xing[len - 1] == 'n')
         {
             string fa = xing.substr(0, len - 4);
             dad[name] = fa;
             sex[name] = 1; // nan
             sex[fa] = 1;
         }
         else if(xing[len - 1] == 'r')
         {
             string fa = xing.substr(0, len - 7);
             dad[name] = fa;
             sex[name] = 0; // nv
             sex[fa] = 1;
         }
         else
         {
             dad[name] = 'A' + i;
             if(xing[len - 1] == 'm')  sex[name] = 1;
             else sex[name] = 0;
         }
     }
     int m; cin >> m;
     for(int i = 0; i < m; i ++)
     {
         string name1, xing1;
         string name2, xing2;
         cin >> name1 >> xing1 >> name2 >> xing2;
         if(dad[name1] == "" || dad[name2] == "")
             cout <<  "NA" << endl;
         else if(sex[name1] == sex[name2])
              cout << "Whatever" << endl;
         else
         {
             map<int, string> sta, stb;
             up(name1, 1, sta);
             up(name2, 1, stb);
             int ff = 0, ed = 0;
             for(auto it : sta)
             {
                 int da = it.first;

                 for(auto pp : stb)
                 {
                     int db = pp.first;
                     if(it.second == pp.second &&  (da < 5 || db < 5))
                     {
                         ff = 1;
                         break;
                     }
                     else if(da > 5 && db > 5)
                     {
                         ed = 1;
                         break;
                     }
                 }
                 if(ff || ed) break;
             }
             if(ff) cout << "No" << endl;
             else cout << "Yes" << endl;
         }
     }
    return 0;
}