[国家集训队2011]公交路线 解题报…

题目:

Z市交通不发达,所有公交路线覆盖的边竟然一个环也不包含,甚至该市的公交路线有可能会分为几个互不连通的块,这可真是不可思议。有一天,你突然听到一条消息,说你的M个同学被困在了Z市里,他们分别要从他们当前所在的点ai移动到他们想去的点bi.于是你立刻调集资料,了解了Z市的形状和公交路线的分布,现在你要算出每个人到达目的地最少要换多少次车,或者告知那个人不能仅用公交车达到目的地。
分析:
先考虑一个询问。假设我们想要从A走到B,像这样:

但如果在某处,“最远的一班车”越过了LCA,那情况就变得不确定了——它的路线有可能继续向上,也有可能折向下,我们先不去考虑它。能够确定的是,如果“最远一班车”达到的最浅节点仍然是LCA的后代,坐这班车一定是最优解。

我们对于A和B都执行“在越过LCA之前走最远”的操作。像这样:

发表评论

电子邮件地址不会被公开。 必填项已用*标注