#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
typedef int Vert;
typedef int Cost;
typedef pair<Cost,Vert> Edge;
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
class FoxMeeting { public:
int maxDistance(vector <int> A, vector <int> B, vector <int> L, vector <int> foxes)
{
// I hate 1-indexed numbering.
for(auto& ai: A) ai--;
for(auto& bi: B) bi--;
for(auto& fi: foxes) fi--;
const int N = A.size()+1;
if(N==1)
return 0;
Graph G(N);
for(int i=0; i<N-1; ++i) {
G[A[i]].emplace_back(L[i], B[i]);
G[B[i]].emplace_back(L[i], A[i]);
}
vector<bool> Foxed(N, false);
for(int fi: foxes)
Foxed[fi] = true;
int best = 0x7fffffff;
for(int C=0; C<N; ++C)
best = min(best, solve_centered(G, C, Foxed));
return best;
}
int solve_centered(const Graph& G, int Root, const vector<bool>& Foxed)
{
int L=-1, R=5000000; // (L,R)
while(R-L>1) {
int C = (L+R)/2;
(can(G, Root, Foxed, C) ? R : L) = C;
}
return R;
}
bool can(const Graph& G, int Root, const vector<bool>& Foxed, int MaxMove) {
enum State {FREE, MUSTBEFILLED, BAD};
typedef pair<State, vector<Cost>> Result;
function<Result(Vert,Vert)> rec;
rec = [&](Vert p, Vert v)->Result {
Cost parent_edge = 0;
bool must_fill = false;
vector<Cost> reached;
for(auto& e: G[v])
if(e.second != p) {
Result sr = rec(v, e.second);
if(sr.first == BAD)
return Result(BAD, vector<Cost>());
if(sr.first == MUSTBEFILLED)
must_fill = true;
reached.insert(reached.end(), sr.second.begin(), sr.second.end());
} else {
parent_edge = e.first;
}
if(Foxed[v])
reached.emplace_back(MaxMove);
sort(reached.rbegin(), reached.rend());
if(must_fill) {
if(reached.empty())
return Result(BAD, vector<Cost>());
reached.pop_back();
}
vector<Cost> rr;
for(auto& ri: reached)
if(ri - parent_edge < 0)
must_fill = true;
else
rr.push_back(ri-parent_edge);
return Result(must_fill ? MUSTBEFILLED : FREE, rr);
};
Result r = rec(-1, Root);
return (r.first != BAD);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, FoxMeeting().maxDistance(A, B, L, foxes));}
int main(){
CASE(0)
int A_[] = {1};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = {5};
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = {1, 2};
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = 0;
END
CASE(1)
int A_[] = {1, 2};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2, 3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = {1, 1};
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = {1, 3};
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = 1;
END
CASE(2)
int A_[] = {1, 2};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {2, 3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = {1, 1};
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = {1, 2, 3};
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = 0;
END
CASE(3)
int A_[] = {10,8,3,7,2,6,9,1,4};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {5,5,8,10,5,5,6,10,3};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = {71846,10951,42265,37832,29439,95676,83661,28186,21216};
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = {1,2,3,4,5,6,7,8,9,10};
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = 0;
END
CASE(4)
int A_[] = {8,15,22,24,2,25,13,26,18,4,9,29,1,12,3,16,14,21,19,27,17,7,20,10,30,11,6,5,23};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {28,28,8,8,28,28,25,2,13,24,24,22,22,29,4,22,8,4,1,24,21,14,18,16,13,21,14,1,25};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = {79374,40629,43195,73589,24200,63937,35339,7598,65109,51764,11142,84017,51078,58051,81387,22035,34883,92710,52283,57337,79309,3383,41904,35839,38242,43208,82062,24676,71838};
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = {3,5,7,9,10,14,17,19,20,21,24,25,28};
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = 107013;
END
CASE(5)
int A_[] = {34,14,22,9,24,19,11,37,33,21,5,30,1,43,7,31,45,27,6,12,13,35,23,47,49,50,26,40,16,10,48,25,29,15,28,46,4,20,44,17,39,32,38,2,42,8,36,3,41};
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = {18,18,18,14,9,34,9,24,34,11,18,14,21,21,43,1,22,7,1,30,14,33,13,18,9,5,1,1,26,19,50,33,50,40,29,48,50,37,16,40,48,14,30,22,47,37,7,50,6};
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = {22051,11109,85275,6691,43705,47374,27748,5411,62549,84079,89542,38006,82198,24083,16847,66335,3542,72495,37378,73973,85703,51682,68688,94295,31337,
90071,99317,63484,43244,99079,55857,34503,79709,82140,91137,27033,91599,61168,52345,49569,58919,38133,43361,
40718,2115,79278,88841,40966,42023};
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = {5,12,13,18,23,27,28,29,32,33,34,35,36,37,40,42,43,47,48,49,50};
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = 89342;
END
/*
CASE(6)
int A_[] = ;
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = ;
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = ;
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = ;
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = ;
END
CASE(7)
int A_[] = ;
vector <int> A(A_, A_+sizeof(A_)/sizeof(*A_));
int B_[] = ;
vector <int> B(B_, B_+sizeof(B_)/sizeof(*B_));
int L_[] = ;
vector <int> L(L_, L_+sizeof(L_)/sizeof(*L_));
int foxes_[] = ;
vector <int> foxes(foxes_, foxes_+sizeof(foxes_)/sizeof(*foxes_));
int _ = ;
END
*/
}
// END CUT HERE