#include #include "testlib.h" using namespace std; using P = pair; const long long LM = 1LL << 60; // begin constraints const int MIN_N = 2; const int MAX_N = 3000; const int MIN_Q = 2; const int MAX_Q = 3000; const int MIN_C = 1; const int MAX_C = 1000000000; const int MIN_L = 1; const int MAX_L = 1000000000; // end constraints class union_find { int num; vector par, rank; public: union_find(int n) : num(n), par(vector(n)), rank(vector(n)) { for (int i = 0; i < n; ++i) par[i] = i; } private: int find(int x) { return par[x] == x ? x : (par[x] = find(par[x])); } public: bool unite(int x, int y) { x = find(x); y = find(y); if (x == y) return false; --num; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y]) ++rank[x]; } return true; } }; vector> edge; long long dfs(int p, int par, int to) { if (p == to) return 0; for (auto& e : edge[p]) { if (e.second == par) continue; long long d = dfs(e.second, p, to) + e.first; if (d < LM) return d; } return LM; } vector dp; long long dfs(int p, int par, long long l, long long ds) { dp[p] += min(l, ds); for (auto& e : edge[p]) { if (e.second == par) continue; dp[p] = min(dp[p], dfs(e.second, p, l + e.first, ds)); } return dp[p]; } int main(int argc, char** argv) { registerValidation(argc, argv); int n = inf.readInt(MIN_N, MAX_N, "N"); inf.readSpace(); int q = inf.readInt(MIN_Q, MAX_Q, "Q"); inf.readSpace(); int c = inf.readInt(MIN_C, MAX_C, "C"); inf.readEoln(); edge = vector>(n); union_find uf(n); for (int i = 0; i < n - 1; ++i) { int u = inf.readInt(1, n, "U"); inf.readSpace(); int v = inf.readInt(1, n, "V"); inf.readSpace(); int l = inf.readInt(MIN_L, MAX_L, "L"); inf.readEoln(); --u; --v; ensure(uf.unite(u, v)); edge[u].emplace_back(l, v); edge[v].emplace_back(l, u); } vector x = inf.readInts(q, 1, n, "X"); inf.readEoln(); for (int i = 0; i < q - 1; ++i) { ensure(x[i] != x[i + 1]); } inf.readEof(); for (int i = 0; i < q; ++i) { --x[i]; } dp = vector(n, LM); dp[x[0]] = 0; for (int i = 1; i < q; ++i) { long long d = dfs(x[i - 1], -1, x[i]); dfs(x[i], -1, c, d); } long long ans = LM; for (int i = 0; i < n; ++i) { ans = min(ans, dp[i]); } cout << ans << '\n'; return 0; }