#![allow(unused_imports)] use std::cmp::*; use std::collections::*; use std::io::Write; use std::ops::Bound::*; #[allow(unused_macros)] macro_rules! debug { ($($e:expr),*) => { #[cfg(debug_assertions)] $({ let (e, mut err) = (stringify!($e), std::io::stderr()); writeln!(err, "{} = {:?}", e, $e).unwrap() })* }; } fn main() { let v = read_vec::(); let (n, q, c) = (v[0] as usize, v[1] as usize, v[2]); let mut edges = vec![vec![]; n]; let mut graph = vec![vec![]; n]; for i in 0..n - 1 { let v = read_vec::(); let (a, b, c) = (v[0] as usize - 1, v[1] as usize - 1, v[2]); edges[a].push(Edge { to: b, cost: c }); edges[b].push(Edge { to: a, cost: c }); graph[a].push(b); graph[b].push(a); } let x = read_vec::() .iter() .map(|&x| x - 1) .collect::>(); let mut dp = vec![std::i64::MAX; n]; let mut cur = x[0]; dp[cur] = 0; for to in x.into_iter().skip(1) { let d = solve(&edges, to); let mut next = vec![std::i64::MAX; n]; for i in 0..n { if dp[i] == std::i64::MAX { continue; } next[i] = min(dp[i] + d[cur], dp[i] + c + d[i]); } let mut tree: Vec> = vec![Vec::new(); n]; let mut parent_dict: HashMap = HashMap::new(); make_tree(to, n, &graph, &mut tree, &mut parent_dict); let mut topological_sorted_indexes = vec![to]; topological_dfs(to, &tree, &mut topological_sorted_indexes); for &ti in topological_sorted_indexes.iter().rev() { if ti == to { break; } if next[ti] == std::i64::MAX { continue; } let x = parent_dict[&ti]; next[x] = min(next[x], next[ti]); } // debug!(next); cur = to; dp = next; } let ans = dp.iter().min().unwrap(); println!("{}", ans); } fn read() -> T { let mut s = String::new(); std::io::stdin().read_line(&mut s).ok(); s.trim().parse().ok().unwrap() } fn read_vec() -> Vec { read::() .split_whitespace() .map(|e| e.parse().ok().unwrap()) .collect() } fn make_tree( cur_idx: usize, parent_idx: usize, edges: &Vec>, tree: &mut Vec>, parent_dict: &mut HashMap, ) { for child_idx in edges[cur_idx].iter() { if *child_idx == parent_idx { continue; } tree[cur_idx].push(*child_idx); parent_dict.insert(*child_idx, cur_idx); make_tree(*child_idx, cur_idx, edges, tree, parent_dict); } } fn topological_dfs(cur_idx: usize, tree: &Vec>, result: &mut Vec) { for child_idx in tree[cur_idx].iter() { result.push(*child_idx); topological_dfs(*child_idx, tree, result); } } type Cost = i64; const INF: Cost = 100000_00000_00000; #[derive(PartialEq, Debug)] struct MinInt { value: Cost, } impl Eq for MinInt {} impl PartialOrd for MinInt { fn partial_cmp(&self, other: &Self) -> Option { other.value.partial_cmp(&self.value) } } impl Ord for MinInt { fn cmp(&self, other: &MinInt) -> Ordering { other.value.partial_cmp(&self.value).unwrap() } } fn make_pair(x: Cost, y: usize) -> (MinInt, usize) { (MinInt { value: x }, y) } #[derive(Debug, Clone)] struct Edge { to: usize, cost: Cost, } fn solve(edges: &Vec>, start_idx: usize) -> Vec { let num_apexes = edges.len(); let mut d = vec![INF; num_apexes]; d[start_idx] = 0; let mut que = BinaryHeap::new(); que.push(make_pair(0, start_idx)); while let Some((u, v)) = que.pop() { if d[v] < u.value { continue; } for e in &edges[v] { if d[v] != INF && d[e.to] > d[v] + e.cost { d[e.to] = d[v] + e.cost; que.push(make_pair(d[e.to], e.to)); } } } d }