#P9174. Slipper
Slipper
Slipper
题目描述
Gi 是一个淘气的孩子,经常做一些奇怪的事情。因此,他的父亲决定和他玩一个游戏。
Gi 的父亲是一位资深魔法师,他把 Gi 和 Gi 的拖鞋传送进了一座迷宫。为了简化问题,我们将迷宫视为一棵有 个节点、以节点 为根的树。记 为节点 的深度。Gi 最初位于节点 ,他的拖鞋位于节点 。在树上经过一条边需要消耗 单位能量。
Gi 也是一位小魔法师!如果两个节点的深度之差等于 ,他就可以使用魔法在这两个节点之间传送。也就是说,对于满足 的两个节点 ,Gi 可以从 传送到 ,也可以从 传送到 。每次使用魔法需要消耗 单位能量。魔法的使用次数不限。
Gi 希望以最少的能量拿到他的拖鞋。
输入格式
输入包含多组测试数据。第一行包含测试数据组数 ,其中 。
对于每组测试数据:
第一行包含一个整数 ,表示树的节点数,。
接下来 行,每行包含三个整数 ,表示节点 和 之间有一条边,经过这条边需要消耗 单位能量。其中 ,。
接下来一行包含两个整数 ,其中 ,。
最后一行包含两个正整数 ,分别表示 Gi 和拖鞋的位置。其中 ,,保证 。
输出格式
对于每组测试数据,输出一行一个整数,表示 Gi 所需消耗的最少能量。
样例
1
6
6 1 2
3 5 2
2 4 6
5 2 2
5 6 20
3 8
6 5
12
提示
样例 1:Gi 可以先从节点 走到节点 ,消耗 单位能量。然后从节点 传送到节点 ,消耗 单位能量。最后从节点 走到节点 ,消耗 单位能量。
总消耗为 。
来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。