← 返回题目列表

Codeforces · 868/E

E. 警察和一棵树

中文机器翻译题面 查看原题

给你一棵树(无环的无向连通图),顶点编号为 1 到 n,第 i 条边的长度为 wi。在顶点 s 中有一名警察,在顶点 x1, x2, ..., xm (xj ≠ s) m 处有罪犯。

警察可以以速度1沿着边缘行走,罪犯可以以任意大的速度移动。如果某个罪犯在某个时刻与警察处于同一地点,他会立即被警察抓住。假设每个人都表现最佳(即罪犯最大化该时间,警察最小化该时间),确定警察抓获所有罪犯所需的时间。每个人在任何时候都知道其他人的立场。

输入

第一行包含单个整数 n (1 ≤ n ≤ 50) — 树中的顶点数。接下来的 n - 1 行每行包含三个整数:ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 50) 表示边及其长度。保证给定的图是一棵树。

下一行包含单个整数 s (1 ≤ s ≤ n) — 警察开始的顶点数。

下一行包含单个整数 m (1 ≤ m ≤ 50) — 罪犯数量。下一行包含 m 个整数 x1, x2, ..., xm (1 ≤ xj ≤ n, xj ≠ s) - 犯罪分子所在的顶点数。 xj 不一定不同。

输出

如果警察抓不到罪犯,则打印单行“恐怖分子获胜”(不带引号)。

否则,打印单个整数——抓获所有罪犯所需的时间。

示例

输入 #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并抓住剩下的罪犯。