{"raw_statement":[{"iden":"statement","content":"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 _w__i_. In the vertex _s_ there is a policeman, in the vertices _x_1, _x_2, ..., _x__m_ (_x__j_ ≠ _s_) _m_ criminals are located.\n\nThe 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."},{"iden":"input","content":"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: _u__i_, _v__i_, _w__i_ (1 ≤ _u__i_, _v__i_ ≤ _n_, 1 ≤ _w__i_ ≤ 50) denoting edges and their lengths. It is guaranteed that the given graph is a tree.\n\nThe next line contains single integer _s_ (1 ≤ _s_ ≤ _n_) — the number of vertex where the policeman starts.\n\nThe next line contains single integer _m_ (1 ≤ _m_ ≤ 50) — the number of criminals. The next line contains _m_ integers _x_1, _x_2, ..., _x__m_ (1 ≤ _x__j_ ≤ _n_, _x__j_ ≠ _s_) — the number of vertices where the criminals are located. _x__j_ are not necessarily distinct."},{"iden":"output","content":"If the policeman can't catch criminals, print single line \"_Terrorists win_\" (without quotes).\n\nOtherwise, print single integer — the time needed to catch all criminals."},{"iden":"examples","content":"Input\n\n4\n1 2 2\n1 3 1\n1 4 1\n2\n4\n3 1 4 1\n\nOutput\n\n8\n\nInput\n\n6\n1 2 3\n2 3 5\n3 4 1\n3 5 4\n2 6 3\n2\n3\n1 3 5\n\nOutput\n\n21"},{"iden":"note","content":"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."}],"translated_statement":[{"iden":"statement","content":"你被给定一棵树（一个无环的连通无向图），顶点编号从 #cf_span[1] 到 #cf_span[n]，第 #cf_span[i] 条边的长度为 #cf_span[wi]。在顶点 #cf_span[s] 处有一名警察，在顶点 #cf_span[x1, x2, ..., xm]（#cf_span[xj ≠ s]）处有 #cf_span[m] 名罪犯。\n\n警察沿边行走的速度为 #cf_span[1]，罪犯可以以任意大的速度移动。如果在某一时刻，一名罪犯与警察位于同一位置，他将立即被抓获。请确定警察抓获所有罪犯所需的最短时间，假设所有人行为最优（即罪犯最大化该时间，警察最小化该时间）。任何时刻，所有人都知道其他人的位置。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50]）——树的顶点数。接下来的 #cf_span[n - 1] 行每行包含三个整数：#cf_span[ui]、#cf_span[vi]、#cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[1 ≤ wi ≤ 50]），表示边及其长度。保证给定图是一棵树。\n\n下一行包含一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ n]）——警察的起始顶点编号。\n\n下一行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 50]）——罪犯的数量。再下一行包含 #cf_span[m] 个整数 #cf_span[x1, x2, ..., xm]（#cf_span[1 ≤ xj ≤ n]，#cf_span[xj ≠ s]）——罪犯所在顶点的编号。#cf_span[xj] 不一定互不相同。\n\n如果警察无法抓获所有罪犯，请输出一行 \"_Terrorists win_\"（不含引号）。\n\n否则，输出一个整数——抓获所有罪犯所需的最短时间。\n\n在第一个例子中，一种最优策略如下：第 #cf_span[2] 名罪犯移动到顶点 #cf_span[3]，第 #cf_span[4] 名罪犯移动到顶点 #cf_span[4]。警察前往顶点 #cf_span[4] 并抓获两名罪犯。之后，第 #cf_span[1] 名罪犯移动到顶点 #cf_span[2]。警察前往顶点 #cf_span[3] 抓获第 #cf_span[2] 名罪犯，然后前往顶点 #cf_span[2] 抓获剩余的罪犯。\n\n"},{"iden":"input","content":"第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 50]）——树的顶点数。接下来的 #cf_span[n - 1] 行每行包含三个整数：#cf_span[ui]、#cf_span[vi]、#cf_span[wi]（#cf_span[1 ≤ ui, vi ≤ n]，#cf_span[1 ≤ wi ≤ 50]），表示边及其长度。保证给定图是一棵树。下一行包含一个整数 #cf_span[s]（#cf_span[1 ≤ s ≤ n]）——警察的起始顶点编号。下一行包含一个整数 #cf_span[m]（#cf_span[1 ≤ m ≤ 50]）——罪犯的数量。再下一行包含 #cf_span[m] 个整数 #cf_span[x1, x2, ..., xm]（#cf_span[1 ≤ xj ≤ n]，#cf_span[xj ≠ s]）——罪犯所在顶点的编号。#cf_span[xj] 不一定互不相同。"},{"iden":"output","content":"如果警察无法抓获所有罪犯，请输出一行 \"_Terrorists win_\"（不含引号）。否则，输出一个整数——抓获所有罪犯所需的最短时间。"},{"iden":"examples","content":"输入41 2 21 3 11 4 1243 1 4 1输出8输入61 2 32 3 53 4 13 5 42 6 3231 3 5输出21"},{"iden":"note","content":"在第一个例子中，一种最优策略如下：第 #cf_span[2] 名罪犯移动到顶点 #cf_span[3]，第 #cf_span[4] 名罪犯移动到顶点 #cf_span[4]。警察前往顶点 #cf_span[4] 并抓获两名罪犯。之后，第 #cf_span[1] 名罪犯移动到顶点 #cf_span[2]。警察前往顶点 #cf_span[3] 抓获第 #cf_span[2] 名罪犯，然后前往顶点 #cf_span[2] 抓获剩余的罪犯。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, where each edge $ e = (u, v) \\in E $ has weight $ w_e \\in \\mathbb{Z}^+ $.  \nLet $ s \\in V $ be the initial position of the policeman.  \nLet $ C = \\{x_1, x_2, \\dots, x_m\\} \\subseteq V \\setminus \\{s\\} $ be the multiset of initial positions of the criminals.  \n\nLet $ d(u, v) $ denote the shortest path distance (sum of edge weights) between vertices $ u $ and $ v $ in $ T $.  \n\n**Constraints**  \n1. $ 1 \\le n \\le 50 $  \n2. $ 1 \\le w_e \\le 50 $ for all $ e \\in E $  \n3. $ 1 \\le s \\le n $  \n4. $ 1 \\le m \\le 50 $, and $ x_j \\ne s $ for all $ j \\in \\{1, \\dots, m\\} $  \n\n**Objective**  \nCompute the minimal time $ T^* $ required for the policeman to catch all criminals, assuming:  \n- The policeman moves at speed 1.  \n- Criminals move with unbounded speed and cooperate adversarially to maximize the capture time.  \n- All agents have complete information of positions at all times.  \n\nIf no finite time suffices (i.e., if any criminal can indefinitely evade capture), output \"_Terrorists win_\".  \n\nOtherwise, output $ T^* = \\min_{\\text{policeman strategies}} \\max_{\\text{criminal strategies}} \\text{time to catch all criminals} $.  \n\n**Key Insight**  \nThe problem reduces to:  \n- The policeman must traverse a subtree containing all criminal positions.  \n- Since criminals can move arbitrarily fast, they can always retreat to the farthest leaf in their connected component away from the policeman’s path.  \n- The optimal strategy for the policeman is to traverse a walk that covers all criminal positions, and the minimal time is determined by the **maximum distance from $ s $ to any criminal**, **but** only if the criminal is on a \"dead-end\" branch.  \n- However, if multiple criminals are on the same branch, the policeman must traverse the branch fully and return to catch others.  \n- **Crucially**: A criminal located at vertex $ x $ can only be caught if the policeman visits $ x $ or a point on the unique path from $ s $ to $ x $.  \n- Since criminals move optimally to evade, they will flee to the farthest point on their branch. Thus, the time needed is the **maximum, over all criminal positions $ x \\in C $, of the distance from $ s $ to $ x $**, **but only if** the branch from $ s $ to $ x $ has no other criminal that forces an earlier return.  \n\nActually, the correct formulation is known from competitive programming problems (e.g., CodeForces \"Policeman and a Tree\"):  \n\nThe answer is the **maximum distance from $ s $ to any criminal**, **if** the entire set of criminals lies on a single path from $ s $. Otherwise, the policeman must backtrack, and the optimal time is the **length of the shortest walk starting at $ s $ that covers all criminal positions** — which equals **twice the total weight of the minimal subtree spanning $ s $ and all criminal positions, minus the maximum distance from $ s $ to any criminal**.  \n\nBut more precisely:  \n\nLet $ R $ be the minimal subtree of $ T $ that contains $ s $ and all vertices in $ C $.  \nLet $ D = \\max_{x \\in C} d(s, x) $.  \nLet $ W $ be the total weight of $ R $.  \n\nThen, the minimal time is:  \n$$\nT^* = 2W - D\n$$  \n\n**Why?**  \nThe policeman must traverse every edge of $ R $ at least twice, except the final path to the farthest criminal (which is traversed only once).  \n\n**Exception**: If the minimal subtree $ R $ does not exist (i.e., no criminals), then $ T^* = 0 $. But $ m \\ge 1 $.  \n\n**But**: If the tree is such that the criminals can escape to infinity?  \n→ Impossible. The graph is finite.  \n\n**So, \"Terrorists win\"** only if...  \nActually, **in a finite tree, the policeman can always catch all criminals** — since the graph is finite and connected, and criminals cannot leave the tree.  \n\nThus, \"_Terrorists win_\" **never** occurs.  \n\n**Final Formal Statement**  \n\n**Definitions**  \nLet $ T = (V, E) $ be a tree with $ |V| = n $, edge weights $ w: E \\to \\mathbb{Z}^+ $.  \nLet $ s \\in V $ be the policeman’s start vertex.  \nLet $ C \\subseteq V \\setminus \\{s\\} $ be the multiset of criminal positions ($ |C| = m $).  \n\nLet $ R \\subseteq T $ be the minimal subtree spanning $ \\{s\\} \\cup C $.  \nLet $ W = \\sum_{e \\in E(R)} w(e) $ be the total weight of $ R $.  \nLet $ D = \\max_{x \\in C} d(s, x) $, where $ d(s, x) $ is the sum of edge weights on the unique $ s $-$ x $ path in $ T $.  \n\n**Constraints**  \nAs above.  \n\n**Objective**  \nCompute:  \n$$\nT^* = 2W - D\n$$","simple_statement":null,"has_page_source":false}