神秘国度的爱情故事

某个太空神秘国度中有很多美丽的小村，从太空中可以想见，小村间有路相连，更精确一点说，任意两村之间有且仅有一条路径。小村 A 中有位年轻人爱上了自己村里的美丽姑娘。每天早晨，姑娘都会去小村 B 里的面包房工作，傍晚 6 点回到家。年轻人终于决定要向姑娘表白，他打算在小村 C 等着姑娘路过的时候把爱慕说出来。问题是，他不能确定小村 C 是否在小村 B 到小村 A 之间的路径上。你可以帮他解决这个问题吗？

输入要求：输入由若干组测试数据组成。每组数据的第 1 行包含一正整数 N ( l 《 N 《 50000 ) , 代表神秘国度中小村的个数，每个小村即从0到 N - l 编号。接下来有 N -1 行输入，每行包含一条双向道路的两个端点小村的编号，中间用空格分开。之后一行包含一正整数 M ( l 《 M 《 500000 ) ，代表着该组测试问题的个数。接下来 M 行，每行给出 A 、 B 、 C 三个小村的编号，中间用空格分开。当 N 为 O 时，表示全部测试结束，不要对该数据做任何处理。

输出要求：对每一组测试给定的 A 、 B 、C，在一行里输出答案，即：如果 C 在 A 和 B 之间的路径上，输出 Yes ，否则输出 No。

示例代码如下：

#include <iostream>using namespace std;#define MAXSIZE 50000using namespace std;//村子树节点，数据域有入栈出栈时间域、村子编号域//树采用孩子兄弟链存储结构typedef struct Village{int num;//村子编号int inid;//深度优先遍历入栈记录int outid;//节点出栈记录struct Village *firstchild;struct Village *nextcousin;}VillageNode;typedef struct{int top;VillageNode *villages[MAXSIZE];}Stack;Stack *s = (Stack *)malloc(sizeof(Stack));int id = 0;//记录栈访问编号void pushStack(VillageNode *p);//将*p节点压入栈void popStack(VillageNode *p);//将栈顶元素弹出,并将地址保存至p指针VillageNode* dfsfind(VillageNode* root, int va, int vb);//深度查找从A村到B村的路径int addNode(VillageNode *root, int a, int b);//增加结点间路径void dfs(VillageNode *root);//深度递归遍历void ifwait(int va, int vb, int vc);//二分查找//将*p节点压入栈void pushStack(VillageNode *p)//压栈{s->villages[++s->top] = p;id++;//栈访问次数加1p->inid = id; //记录入栈}//将栈顶元素弹出,并将地址保存至p指针void popStack(VillageNode *p)//出栈{if (s->top > -1){p = s->villages[s->top];s->top--;id++;//栈访问次数加1p->outid = id;}}VillageNode* dfsfind(VillageNode* root, int va){if (root == NULL)//当前节点 为空，返回NULLreturn NULL;int v = root->num;VillageNode *p, *q;if (va == v)//如果找到原先既有的节点，则返回该节点的指针return root;q = dfsfind(root->firstchild, va); //递归访问孩子节点if (q != NULL)return q;p = root->nextcousin;while (p != NULL){q = dfsfind(p, va);if (q != NULL)return q;p = p->nextcousin;}return NULL;//当访问过的节点达到总数仍没有找到va 或 vb节点时，返回NULL}int addNode(VillageNode *root, int va, int vb){VillageNode *vp = dfsfind(root, va); //寻找编号为a的村子VillageNode *p, *q;if (vp != NULL){if (vp->num == va)//找到村子A，遍历村子A孩子节点{p = vp->firstchild;q = vp;if (p == NULL)//当vp节点下没有孩子节点时{VillageNode *vn = (VillageNode*)malloc(sizeof(VillageNode));vn->firstchild = NULL;vn->nextcousin = NULL;vn->num = vb;q->firstchild = vn;return 1;}while (p != NULL){if (p->num == vb) //当村子A存在到村子B的路时返回0return 0;q = p;//记录当前节点p = p->nextcousin; //p指向下一个节点}VillageNode *vn = (VillageNode*)malloc(sizeof(VillageNode));vn->firstchild = NULL;vn->nextcousin = NULL;vn->num = vb;q->nextcousin = vn;return 1;}}return -1;}void dfs(VillageNode *root)//深度遍历{pushStack(root);VillageNode *p;p = root->firstchild;//指向第一个孩子while (p != NULL)//孩子节点不为空，递归访问孩子节点{dfs(p);p = p->nextcousin;}popStack(p);//弹出栈顶元素return;}void ifwait(VillageNode *root, int va, int vb, int vc){VillageNode *VA = dfsfind(root, va);VillageNode *VB = dfsfind(root, vb);VillageNode *VC = dfsfind(root, vc);if (!VA || !VB || !VC) {cout << "A村、B村或者C村不存在！" << endl;return;}cout << "找到的A,B,C分别为：\t" << VA->num<<'\t'<< VB->num << '\t' << VC->num << '\t';if (va == vc || vb == vc) {cout << "YES" << endl;}else if ((VC->inid < VA->inid && VC->outid > VA->outid) && (VC->inid < VB->inid && VC->outid > VB->outid)) //C节点的入出栈区间包含A、B的区间{//当VC是VA和VB的公共祖先时 判断是否是最低公共祖先int a[2][MAXSIZE];//二维数组第一行存放inid 第二行存放outid 每一列对应一个节点 从左到右int min, max;//min：VA、VB入栈最小max：VA、VB出栈最大min = (VA->inid < VB->inid) ? VA->inid : VB->inid;max = (VA->outid > VB->outid) ? VA->outid : VB->outid;VillageNode *p = VC->firstchild;int i = 0;while (p != NULL)//遍历VC节点所有的孩子节点 并把孩子们的入出栈编号存入数组{a[0][i] = p->inid;a[1][i] = p->outid;i++;p = p->nextcousin;}//二分查找[min,max]区间是否包含在其中一个孩子节点中int low = 0, high = i - 1, mid;while (low <= high){mid = (low + high) / 2;if (a[0][mid] <= min && a[1][mid] >= max)//查找到有区间包含[min,max]区间时，VC不是VA和VB的最低公共祖先，跳出循环{cout << "No" << endl;return;}if (a[0][mid] > min)//继续在a[0][low...mid-1]中查找high = mid - 1;else//继续在a[0][mid+1...high]中查找low = mid + 1;}cout << "YES" << endl;//当查找结束仍没有找到该区间，说明VC是VA、B的最低公共祖先}else if ((VC->inid < VA->inid && VC->outid > VA->outid) || (VC->inid < VB->inid && VC->outid > VB->outid)) //或VC节点的入出栈时间区间包含VB的区间{//VC是VA、VB其中一个节点的祖先，存在A-C-B的路径cout << "YES" << endl;}else //当VC不是VA的祖先而且不是VB节点的祖先时,不存在A-C-B的路径cout << "No" << endl;return;}int main(){cout << "——————————————————————————————" << endl;cout << "\t\t神秘国度的爱情故事" << endl;cout << "——————————————————————————————" << endl;int N, M,a,b;int testA[MAXSIZE], testB[MAXSIZE], testC[MAXSIZE];//分别存放A,B,C测试组printf("请输入小村个数：\n");cin >> N;VillageNode *root = (VillageNode *)malloc(sizeof(VillageNode)); //建立指向深度优先搜索树的指针并建立深度优先搜素树root->firstchild = NULL;root->nextcousin = NULL;root->num = 0;printf("接下来，请依次输入包含一条双向道路的两个端点小村的编号：\n");for(int i = 0; i < N-1; i++){cin >> a >> b; //读取边信息int flag = addNode(root, a, b);if (flag == 0){cout << "小村" << a << "到小村" << b << "的路径已存在，无需再次输入，本次输入将不会被记录。" << endl;N++;}else if (flag == 1){}elsecout << "录入失败！" << a << b << endl;}s->top = -1;dfs(root);//深度遍历一遍树cout<<"请输入A,B,C样例个数：\n";cin>>M;cout << "请依次输入A,B,C样例：\n";for (int i = 0; i < M; i++) {//用三个数组分别存储各个对应的A、B、Ccin >> testA[i] >> testB[i] >> testC[i];}for(int i = 0; i < M; i++){ifwait(root, testA[i], testB[i], testC[i]);}return 0;}