HBC20114[HNOI2015]接水果题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

风见幽香非常喜欢玩一个叫做 osu!

风见幽香非常喜欢玩一个叫做 osu!的游戏，其中她最喜欢玩的模式就是接水果。由于她已经DT FC 了The big black, 她觉得这个游戏太简单了，于是发明了一个更加难的版本。 首先有一个地图，是一棵由 n 个顶点、n-1 条边组成的树（例如图 1给出的树包含 8 个顶点、7 条边）。 这颗树上有 P 个盘子，每个盘子实际上是一条路径（例如图 1 中顶点 6 到顶点 8 的路径），并且每个盘子还有一个权值。第 i 个盘子就是顶点ai到顶点bi的路径(由于是树，所以从ai到bi的路径是唯一的)，权值为ci。 接下来依次会有Q个水果掉下来，每个水果本质上也是一条路径，第i 个水果是从顶点 ui 到顶点vi 的路径。 幽香每次需要选择一个盘子去接当前的水果：一个盘子能接住一个水果，当且仅当盘子的路径是水果的路径的子路径（例如图1中从 3到7 的路径是从1到8的路径的子路径）。这里规定:从a 到b的路径与从b到 a的路径是同一条路径。 当然为了提高难度，对于第 i 个水果，你需要选择能接住它的所有盘子中，权值第 ki 小的那个盘子，每个盘子可重复使用（没有使用次数的上限：一个盘子接完一个水果后，后面还可继续接其他水果，只要它是水果路径的子路径）。幽香认为这个游戏很难，你能轻松解决给她看吗？  

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC20114[HNOI2015]接水果题解