P1045战争游戏（wargame）

【题目背景】

道路与传信系统准备完成后，Ehundategh 与 tfbz 决定用一场模拟对抗检验新的防线。tfbz 负责布置基地与特工的初始位置，Ehundategh 负责指挥特工切断全部情报链路。

【题目描述】

Ehundategh 在与 tfbz 玩一场战争游戏，这个游戏是这样的，tfbz 有一个基地，这个基地由 $n$ 个据点 $n-1$ 条连接据点的双向道路构成一棵树的结构。在这些据点中，$1$ 号据点是 tfbz 的情报中枢，视作整棵树的根节点，而这棵树的叶子节点是该基地的兵营，兵营需要从情报中枢获取情报，在一开始，情报可以顺畅地从情报中枢到任意一个兵营。

Ehundategh 需要做的就是破坏情报链路，他将向 tfbz 的基地中投放了 $m$ 个特工，情报经过特工潜伏的位置时，会被直接截断，形式化地讲，若对于叶子节点 $u$，路径 $1\to u$ 上存在一个潜伏的特工，那么情报便不能运输到 $u$ 节点，而当所有的兵营都无法收到情报时，Ehundategh 的任务就算完成了。但是为了确保公平，这些特工的初始位置不受 Ehundategh 控制，而是由 tfbz 选择，Ehundategh 能做的是指挥特工的行动，这些特工可以沿着双向道路移动，每经过一条双向道路，便会花费道路长度 $w_i$ 的时间。每个特工最后都需要潜伏在某个据点，以阻断情报链路，但他们不能潜伏在 $1$ 号据点，因为 $1$ 号据点的侦察能力很强，他们潜伏在 $1$ 号据点会被发现。

在 $0$ 时刻，所有特工都被投放入 tfbz 的基地，现在，Ehundategh 想知道他至少需要多久才能达成他的目标，若达成不了目标，请输出 Pity!。（注意：所有特工可以同时行动）

【输入格式】

从文件 $\textbf{\textit{wargame.in}}$ 中读入数据。

本题包含多组测试数据。

输入的第一行包含两个非负整数 $c,T$，分别表示测试点编号与测试数据的组数。$c=0$ 表示该测试点为样例。

对于每组测试数据：

第一行包含两个正整数 $n,m$，表示据点个数和特工个数。

接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示一条连接据点 $u$ 和 $v$、长度为 $w$ 的双向道路。

接下来一行包含 $m$ 个整数，表示 tfbz 指定的特工初始位置。

【输出格式】

输出到文件 $\textbf{\textit{wargame.out}}$ 中。

对于每组测试数据输出一行。若 Ehundategh 能够达成目标，输出最短时间，否则输出字符串 Pity!。

【样例 1 输入】

10 224 231 2 141 3 253 4 362 273 181 2 591 3 7102

【样例 1 输出】

132Pity!

【说明/提示】

【样例 1 解释】

第一组测试数据中，一名特工留在据点 $2$，另一名特工从据点 $2$ 移动到据点 $3$，需要 $3$ 单位时间。

【样例 2】

见选手目录下的 $\textbf{\textit{wargame/wargame2.in}}$ 和 $\textbf{\textit{wargame/wargame2.ans}}$。

该组样例符合测试点 $1\sim 5$ 的数据范围。

【样例 3】

见选手目录下的 $\textbf{\textit{wargame/wargame3.in}}$ 和 $\textbf{\textit{wargame/wargame3.ans}}$。

该组样例符合测试点 $6\sim 10$ 的数据范围。

【样例 4】

见选手目录下的 $\textbf{\textit{wargame/wargame4.in}}$ 和 $\textbf{\textit{wargame/wargame4.ans}}$。

该组样例符合测试点 $11\sim 14$ 的数据范围。

【样例 5】

见选手目录下的 $\textbf{\textit{wargame/wargame5.in}}$ 和 $\textbf{\textit{wargame/wargame5.ans}}$。

该组样例符合测试点 $15\sim 19$ 的数据范围。

【样例 6】

见选手目录下的 $\textbf{\textit{wargame/wargame6.in}}$ 和 $\textbf{\textit{wargame/wargame6.ans}}$。

该组样例符合测试点 $20\sim 25$ 的数据范围。

【数据范围】

对于 $100\%$ 的数据，保证 $1\leq T\leq 10$，$2\leq n\leq 5\times 10^4$，$1\leq m\leq n$，单个测试点内 $\sum n\leq 5\times 10^4$，$1\leq u,v\leq n$，$1\leq w<10^9$，所有特工均不位于据点 $1$。

特殊性质 A：保证每组测试数据中，叶子结点数量不超过 $10$。

特殊性质 B：保证据点 $1$ 恰好连接一条道路。

特殊性质 C：保证所有道路都与据点 $1$ 相连。