#[allow(unused_imports)] use std::cmp::*; #[allow(unused_imports)] use std::collections::*; use std::io::{Write, BufWriter}; // https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { ($($r:tt)*) => { let stdin = std::io::stdin(); let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock())); let mut next = move || -> String{ bytes.by_ref().map(|r|r.unwrap() as char) .skip_while(|c|c.is_whitespace()) .take_while(|c|!c.is_whitespace()) .collect() }; input_inner!{next, $($r)*} }; } macro_rules! input_inner { ($next:expr) => {}; ($next:expr,) => {}; ($next:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($next, $t); input_inner!{$next $($r)*} }; } macro_rules! read_value { ($next:expr, ( $($t:tt),* )) => { ($(read_value!($next, $t)),*) }; ($next:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($next, $t)).collect::>() }; ($next:expr, chars) => { read_value!($next, String).chars().collect::>() }; ($next:expr, usize1) => (read_value!($next, usize) - 1); ($next:expr, [ $t:tt ]) => {{ let len = read_value!($next, usize); read_value!($next, [$t; len]) }}; ($next:expr, $t:ty) => ($next().parse::<$t>().expect("Parse error")); } pub struct LCA { st: Vec, par: Vec, jmp: Vec, dep: Vec, } // Constant-factor speedup used in https://codeforces.com/contest/1083/submission/46874242. // Base on HL-decomposition. // par[root] = root should hold. // These functions use O(n) stack space. // Verified by https://codeforces.com/contest/1083/submission/51934575. impl LCA { // For each node, make the most heavy child the first child. fn dfs_left(ch: &mut [Vec], v: usize, sz: &mut [usize], dep: &mut [usize], d: usize) { dep[v] = d; let mut s = 1; for i in 0..ch[v].len() { let w = ch[v][i]; Self::dfs_left(ch, w, sz, dep, d + 1); s += sz[w]; if sz[w] > sz[ch[v][0]] { ch[v].swap(i, 0); } } sz[v] = s; } fn dfs(ch: &[Vec], st: &mut [usize], v: usize, cnt: &mut usize, jmp: &mut [usize]) { st[v] = *cnt; *cnt += 1; if ch[v].len() >= 1 { jmp[ch[v][0]] = jmp[v]; } for &w in &ch[v] { Self::dfs(ch, st, w, cnt, jmp); } } pub fn new(ch: &mut [Vec], par: &[usize], root: usize) -> Self { let n = ch.len(); let mut st = vec![0; n]; let mut cnt = 0; let mut sz = vec![0; n]; let mut jmp = vec![0; n]; let mut dep = vec![0; n]; Self::dfs_left(ch, root, &mut sz, &mut dep, 0); for i in 0..n { jmp[i] = i; } Self::dfs(ch, &mut st, root, &mut cnt, &mut jmp); LCA { st: st, par: par.to_vec(), jmp: jmp, dep: dep, } } pub fn lca(&self, mut x: usize, mut y: usize) -> usize { let jmp = &self.jmp; let st = &self.st; while jmp[x] != jmp[y] { if st[x] < st[y] { std::mem::swap(&mut x, &mut y); } x = self.par[jmp[x]]; } if st[x] < st[y] { x } else { y } } } fn main() { // In order to avoid potential stack overflow, spawn a new thread. let stack_size = 104_857_600; // 100 MB let thd = std::thread::Builder::new().stack_size(stack_size); thd.spawn(|| solve()).unwrap().join().unwrap(); } fn dfs(v: usize, par: usize, g: &[Vec<(usize, i64)>], ch: &mut [Vec], pars: &mut [usize], dist: &mut [i64], d: i64) { dist[v] = d; for &(w, c) in &g[v] { if w == par { pars[v] = w; continue; } ch[v].push(w); dfs(w, v, g, ch, pars, dist, d + c); } } fn solve() { input! { n: usize, q: usize, c: i64, uvl: [(usize1, usize1, i64); n - 1], x: [usize1; q], } let mut g = vec![vec![]; n]; for (u, v, l) in uvl { g[u].push((v, l)); g[v].push((u, l)); } let mut ch = vec![vec![]; n]; let mut pars = vec![0; n]; let mut dist = vec![0; n]; dfs(0, n, &g, &mut ch, &mut pars, &mut dist, 0); let lca = LCA::new(&mut ch, &pars, 0); const INF: i64 = 1 << 60; let mut dp = vec![INF; n]; let mut dpn = 0; for i in 1..q { let mut ep = vec![INF; n]; let mut epn = INF; let mut que = BinaryHeap::new(); for i in 0..n { que.push((Reverse(dp[i]), i)); } que.push((Reverse(dpn - c), x[i - 1])); while let Some((Reverse(d), v)) = que.pop() { if ep[v] <= d { continue; } ep[v] = d; for &(w, c) in &g[v] { que.push((Reverse(d + c), w)); } } let mut dist = vec![INF; n]; let mut que = VecDeque::new(); que.push_back((0, x[i])); while let Some((d, v)) = que.pop_front() { if dist[v] <= d { continue; } dist[v] = d; for &(w, c) in &g[v] { que.push_back((d + c, w)); } } for i in 0..n { ep[i] += c + dist[i]; epn = min(epn, dp[i] + c + dist[i]); } let distx = dist[x[i - 1]]; epn = min(epn, dpn + distx); for i in 0..n { ep[i] = min(ep[i], dp[i] + distx); } dp = ep; dpn = epn; // eprintln!("{:?} {}", dp, dpn); } println!("{}", dpn); }