【luoguP4768】【NOI2018】归程

description

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个 nn 个节点、mm 条边的无向连通图（节点的编号从 11 至 nn）。我们依次用 l,al,a 描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免 的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的OIer，刚参加完ION2018 的他将踏上归程，回到他 温暖的家。 Yazid 的家恰好在魔力之都的 11 号节点。对于接下来 QQ 天，每一天Yazid 都会告诉你他的出发点 vv ，以及当天的水位线pp。 每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着：

车会在新的出发点被准备好。
Yazid 不能利用之前在某处停放的车。
Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。 本题的部分测试点将强制在线，具体细节请见【输入格式】和【子任务】。

kruskal构造树

• 首先得先学这个东东；可以按照$kruskal$建$MST$的思想来建出一个无向图的$kruskal$构造树

• 具体就是按边长度排序后，若边$(x,y)$中$x,y$不连通，建一个新点，新点点权设为边权，把两个集合连到新点上

• 若边升序排序，则对于$(u,v)$两点，$LCA(u,v)$点权即为原图中$u$到$v$所有路径中最大边权的最小值

• 降序排序则是最小边权的最大值；还有一些有意思的性质，比如构造树是二叉树、大（小）根堆

analysis

• 对于点$x$需要知道$x$可以走到的点都有哪些，若建出海拔的$kruskal$构造树，深度越浅点权越小，就是海拔越小

• 找到构造树中深度最浅且满足海拔恰好$>$