到底爱不爱我

L2-3 到底爱不爱我

古代少女有了心上人时，会悄悄折一条树枝，揪那枝上的叶子，揪一片叶子念一句“爱我”，再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候，看看是停在“爱”还是“不爱”。

但聪明的慧娘一眼洞穿，只要数一下叶子有多少片，根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始，就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫，理科生杀死浪漫。

于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”：

• “专情枝”：是一根有两个分岔的树枝，只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候，这根枝条的根部才传出“爱”；否则树枝根部传出的是“不爱”。
• “博爱枝”：也是一根有两个分岔的树枝，只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候，这根枝条的根部才传出“不爱”；否则树枝根部传出的都是“爱”。
• “情变枝”：是没有分岔的一根直枝，如果一端接到“爱”，另一端必须传出“不爱”；反之如果一端接到“不爱”，另一端则会传出“爱”。

慧娘将这些树枝摆放在院子里，布了一个“情阵”，先选一根特殊的枝条作为初试一枝，从这枝条的根部开始，扩散开去，令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来，在初始一枝的根部，她能得到“爱”还是“不爱”？

输入格式：

输入在第一行中给出正整数 N（≤30），是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行，第 i 行给出第 i 枝的描述，格式为

类型 左分枝连接的编号 右分枝连接的编号

其中 类型 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝，则后面跟的是其唯一末端连接的情枝编号，并没有两个分枝的信息。如果一个分枝是末梢，并没有连接其它枝条，则对应编号为 0。

接下来一行中给出正整数 K（≤30），是慧娘询问的次数。以下 K 行，每行给出一个由 0 和 1 组成的字符串，其中 0 表示“不爱”，1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。（注意：“从左到右”的意思是，我们从初试一枝出发去遍历所有枝条的末梢时，总是遵循先遍历左边情阵、再遍历右边情阵的顺序）

输出格式：

对慧娘的每个询问，如果她在初始一枝的根部能得到“爱”，就输出 Ai；否则输出 BuAi。

输入样例：

6
2 6 4
1 0 0
3 1
2 0 0
3 0
1 5 2
5
11111
00000
11100
10011
01100

输出样例：

BuAi
Ai
Ai
BuAi
BuAi

样例说明：

样例对应的情阵以及慧娘第 3 问的情势如图所示，其中完整的心对应 1，裂开的心对应 0。

递归 

#include "bits/stdc++.h"
using namespace std;
struct node{int type;int l;int r;node (int a = -1, int b = 0, int c = 0){type  = a, l = b, r = c;}}tree[40];
int fa[40];
int dfs(int t){int x, y;if(tree[t].type == -1){scanf("%1d", &x);return x;}x = dfs(tree[t].l);	if(tree[t].type != 3) y = dfs(tree[t].r);if(tree[t].type == 3) return 1 - x;else if(tree[t].type == 2) {if(x + y == 0) return 0;else return 1;}else {if(x + y == 2) return 1;else return 0;}
}int main(){memset(fa, -1, sizeof(fa));int n;cin>>n;int a, b, ro;int xx;for(int i = 1; i <= n; i ++){cin>>tree[i].type;cin>>a;if(a != 0){tree[i].l = a;	fa[a] = i; 	}if(tree[i].type != 3) {cin>>b;if(b != 0){tree[i].r = b;fa[b] = i;}			}	}for(int i = 1; i <= n; i ++) if(fa[i] == -1) ro = i;int m;cin>>m;int x;while(m--){int ans = dfs(ro);if (ans == 1) cout<<"Ai"<<endl;else cout<<"BuAi"<<endl;}return 0;
}