警察与树

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一棵树（一种连通无向无环图），顶点编号从 $1$ 到 $n$，第 $i$ 条边的长度为 $w_{i}$。在顶点 $s$ 处有一名警察，在顶点 $x_{1}, x_{2}, ..., x_{m}$（$x_{j} \ne s$）处有 $m$ 名罪犯。

警察可以以速度 $1$ 沿边行走，罪犯可以以任意大的速度移动。如果某一时刻罪犯与警察处于同一位置，罪犯会立即被警察逮捕。假设所有人都采取最优策略行事（即罪犯尽量拖延被捕时间，警察尽量缩短逮捕时间），请你求出警察抓捕全部罪犯所需的时间。所有人随时都知道彼此的位置。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 50$），表示树的顶点数量。接下来 $n-1$ 行，每行包含三个整数 $u_{i}, v_{i}, w_{i}$（$1 \leq u_{i}, v_{i} \leq n$，$1 \leq w_{i} \leq 50$），表示存在一条长度为 $w_{i}$ 的无向边连接 $u_{i}$ 和 $v_{i}$。保证给定的图是一棵树。

接下来一行包含一个整数 $s$（$1 \leq s \leq n$），表示警察的起始顶点编号。

接下来一行包含一个整数 $m$（$1 \leq m \leq 50$），表示罪犯的数量。下一行包含 $m$ 个整数 $x_{1}, x_{2}, ..., x_{m}$（$1 \leq x_{j} \leq n$, $x_{j} \ne s$），表示罪犯的起始顶点编号。$x_{j}$ 不一定各不相同。

输出格式

如果警察无法抓住所有罪犯，输出一行 "Terrorists win"（不带引号）。

否则，输出一个整数，表示警察抓住所有罪犯所需的最短时间。

样例输入 1

4
1 2 2
1 3 1
1 4 1
2
4
3 1 4 1

样例输出 1

8

样例输入 2

6
1 2 3
2 3 5
3 4 1
3 5 4
2 6 3
2
3
1 3 5

样例输出 2

21

提示

在第一个样例中，一种最优的策略如下：第 $2$ 号罪犯移动到顶点 $3$，第 $4$ 号罪犯移动到顶点 $4$。警察前往顶点 $4$，并同时抓住两名罪犯。之后，第 $1$ 号罪犯移动到顶点 $2$。警察前往顶点 $3$ 抓住第 $2$ 号罪犯，然后再前往顶点 $2$ 抓住剩下的罪犯。

数据范围

对所有数据：$1\le n\le50$，$1\le m\le50$，$1\le w_i\le50$，且 $x_j\ne s$。

各子任务数据彼此独立计分。