数据结构课程设计：神秘国度的爱情故事

神秘国度的爱情故事

题目要求 ：在某个遥远的宇宙国度中，分布着众多风景如画的小村落。从太空俯瞰，这些村落之间通过道路相互连接，更确切地说，任意两个村落之间都存在唯一的一条路径。小村落 A 中有一位年轻人，他深深爱上了同村的一位美丽姑娘。每天清晨，姑娘都会前往小村落 B 的面包房工作，并于傍晚六点准时返回家中。这位年轻人终于下定决心向姑娘表达心意，他计划在小村落 C 等待，当姑娘经过时向她倾诉爱意。然而，他无法确定小村落 B 是否位于从 A 到 C 的必经之路上。你能否帮助他解决这一疑问？

输入 ：第一行给出村庄的总数 M，随后 M-1 行每行包含两个村庄编号 Va 和 Vb，表示这两个村庄是直接相连的。接下来是提问次数 N，之后 N 行每行包含三个整数 va、vb、vc。对于每组询问，若 vb 位于 va 与 vc 之间的必经之路上，则输出 "yes"；否则输出 "No"。

分析

• 题目中存在一个关键信息：任意两个村落之间只存在唯一的一条通路。
  • 这一点很容易让人联想到数据结构中的树型结构，其特性恰好吻合这一描述。
  • 然而结合实际情况分析，村落之间并不存在树结构中节点间的父子层级关系，因此该数据结构实际上表现为无向图，并且不包含环路。
  • 再次回到问题本身，可以将其划分为两个步骤。第一步是确定从A村到C村的