7-10 gg的族谱 dfs

7-10 gg的族谱

gg翻到了家里的族谱，他迫切的想知道关于族谱里每个祖先的曾孙子的信息来计算自己的家族地位。但是整个族谱太庞大了，一个个数是一件很累的工作。gg请求你的帮忙，希望你能帮帮他！

gg家有一个很特殊的规定，就是一个人最多生两个儿子/女儿，如果生了两个以上，就要被逐出家族，永久断绝血缘关系，也就再也不会出现在族谱上。为了方便你更加专注的解决这个问题，gg的朋友小Z已经把族谱里面的每个人编号。你的任务就是计算给定编号的人，他的曾曾曾…曾孙子是谁！
输入格式:

第一行给出一个正整数N（N<=100)表示族谱的总人数！

接下来N行每行包含三个数字num，l，r，分别表示节点编号和它的两个孩子编号，如果不存在则用-1表示！

接下来一行包含一个正整数q，表示询问的数量。（q<=10）

接下来q行，每行包含一个1-N的正整数和一个字符串，表示询问的节点编号，字符串以这样的形式给出：

“mygrandgrandgrand…grandson”

有几个grand，就请你输出他第几代孙子的编号！

值得注意的一点是，son也需要算作一代，这对擅长英语的你应该不会太难！（即grandson代表往下两代，grandgrandson代表往下三代）

题目保证字符串一定以"my"开头，且"grand"一定在"my"和"son"之间，且最多有一个“son”在结尾，但不保证字符串一定有"son"！
输出格式:

请你在一行内升序输出每个询问的对应节点编号！如果不存在对应的节点编号，请你输出"None!!!"

末尾不要有多余的空格！
输入样例:

在这里给出一组输入。例如：

6
1 2 3
2 4 5
3 6 -1
4 -1 -1
5 -1 -1
6 -1 -1
2
1 mygrandson
1 mygrandgrandson

输出样例:

在这里给出相应的输出。例如：

4 5 6
None!!!

#ifdef debug
#include <time.h>
#endif

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <math.h>

#define MAXN ((int)1e5+7)
#define ll long long int
#define INF (0x7f7f7f7f)
#define fori(lef, rig) for(int i=lef; i<=rig; i++)
#define forj(lef, rig) for(int j=lef; j<=rig; j++)
#define fork(lef, rig) for(int k=lef; k<=rig; k++)
#define QAQ (0)

using namespace std;

#define show(x...) \ do { \ cout << "\033[31;1m " << #x << " -> "; \ err(x); \ } while (0)

void err() { cout << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cout << a << ' '; err(x...); }

namespace FastIO{

	char print_f[105];
	void read() {}
	void print() { putchar('\n'); }

	template <typename T, typename... T2>
	   inline void read(T &x, T2 &... oth) {
		   x = 0;
		   char ch = getchar();
		   ll f = 1;
		   while (!isdigit(ch)) {
			   if (ch == '-') f *= -1; 
			   ch = getchar();
		   }
		   while (isdigit(ch)) {
			   x = x * 10 + ch - 48;
			   ch = getchar();
		   }
		   x *= f;
		   read(oth...);
	   }
	template <typename T, typename... T2>
	   inline void print(T x, T2... oth) {
		   ll p3=-1;
		   if(x<0) putchar('-'), x=-x;
		   do{
				print_f[++p3] = x%10 + 48;
		   } while(x/=10);
		   while(p3>=0) putchar(print_f[p3--]);
		   putchar(' ');
		   print(oth...);
	   }
} // namespace FastIO
using FastIO::print;
using FastIO::read;

int cnt = 0;
int n, m, Q, K, tree[MAXN<<2];

vector<int> ans;
void dfs(int u, int level) { //无脑暴力
	if(!u) return ;
	if(level == cnt) {
		ans.push_back(u);
		return ;
	}
	if(tree[u<<1]) dfs(tree[u<<1], level+1);
	if(tree[u<<1|1]) dfs(tree[u<<1|1], level+1);
}

signed main() {
#ifdef debug
	freopen("test", "r", stdin);
	clock_t stime = clock();
#endif
	cin >> n;
	int num, l, r;
	for(int i=1; i<=n; i++) {
		cin >> num >> l >> r;
		if(~l) tree[num<<1] = l;
	   	if(~r) tree[num<<1|1] = r;
	}
	cin >> m;
	int root;
	string str;
	while(m--) {
		cin >> root >> str;
		cnt = 0;
		for(auto ch : str)
			if(ch=='g' || ch=='o') cnt ++; //每个grand和son中g和o唯一
		dfs(root, 0);
		if(ans.empty()) {
			printf("None!!!\n");
		} else {
			int p = 0;
			for(auto v : ans)
				printf("%s%d", p++?" ":"", v);
			printf("\n");
		}
		ans.clear();
	}




#ifdef debug
   clock_t etime = clock();
   printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
#endif 
   return 0;
}