Policeman and a Tree
Contest: Codeforces Round 438 by Sberbank and Barcelona Bootcamp (Div. 1 + Div. 2 combined)
Difficulty rating: 2700
Tags: dp, graphs, trees

You are given a tree (a connected non-oriented graph without cycles) with vertices numbered from 1 to n, and the length of the i-th edge is wi. In the vertex s there is a policeman, in the vertices x1, x2, ..., xm (xj ≠ s) m criminals are located.

The policeman can walk along the edges with speed 1, the criminals can move with arbitrary large speed. If a criminal at some moment is at the same point as the policeman, he instantly gets caught by the policeman. Determine the time needed for the policeman to catch all criminals, assuming everybody behaves optimally (i.e. the criminals maximize that time, the policeman minimizes that time). Everybody knows positions of everybody else at any moment of time.

Input format:
The first line contains single integer n (1 ≤ n ≤ 50) — the number of vertices in the tree. The next n - 1 lines contain three integers each: ui, vi, wi (1 ≤ ui, vi ≤ n, 1 ≤ wi ≤ 50) denoting edges and their lengths. It is guaranteed that the given graph is a tree.

The next line contains single integer s (1 ≤ s ≤ n) — the number of vertex where the policeman starts.

The next line contains single integer m (1 ≤ m ≤ 50) — the number of criminals. The next line contains m integers x1, x2, ..., xm (1 ≤ xj ≤ n, xj ≠ s) — the number of vertices where the criminals are located. xj are not necessarily distinct.

Output format:
If the policeman can't catch criminals, print single line "Terrorists win" (without quotes).

Otherwise, print single integer — the time needed to catch all criminals.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example one of the optimal scenarios is the following. The criminal number 2 moves to vertex 3, the criminal 4 — to vertex 4. The policeman goes to vertex 4 and catches two criminals. After that the criminal number 1 moves to the vertex 2. The policeman goes to vertex 3 and catches criminal 2, then goes to the vertex 2 and catches the remaining criminal.

Example input:
4
1 2 2
1 3 1
1 4 1
2
4
3 1 4 1

Example output:
8

Example input:
6
1 2 3
2 3 5
3 4 1
3 5 4
2 6 3
2
3
1 3 5

Example output:
21

Editorial:
Suppose that the policeman is moving from v to u via the tree edge. The criminals can now assume any positions in two halves of the tree (but cannot travel from one half to another). Let dpe, k, a be the resulting time to catch the criminals if the policeman have just started to travel along a (directed) edge e, there are k criminals in total, and a of them are in the half tree "in front" of the policeman.
If the edge e leads into a leaf of the tree, then the policeman catches everyone in this leaf, and his next step is to go back using the same edge. Otherwise, the criminals must have distributed optimally in the subtrees starting with edges e1, ..., ej. The policeman cannot win within time T if there is a distribution a1, ..., aj with $$\sum a_{i} = a$$ such that dpei, k, ai > T for every i. The optimal value of T can be found with binary search: for a particular T find the smallest ai such that dpei, k, ai > T, and check if $$\sum a_{i} \leq a$$. If this is the case, the criminals can distribute so that it will take  > T time to catch them.
The total complexity of this solution is $${\mathcal O}(n^{2}m^{2}\log A)$$, since we have O(nm2) DP states, with each state having O(n) transitions, and the last factor corresponding to binary search on the answer (assuming the answer is at most A).