// ---------- begin Lazy Segment Tree ---------- pub trait TE { type T: Clone; type E: Clone; fn fold(l: &Self::T, r: &Self::T) -> Self::T; fn eval(x: &Self::T, f: &Self::E) -> Self::T; fn merge(g: &Self::E, h: &Self::E) -> Self::E; fn e() -> Self::T; fn id() -> Self::E; } pub struct LazySegmentTree { size: usize, bit: usize, a: Vec<(R::T, R::E)>, } impl LazySegmentTree { pub fn new(n: usize) -> LazySegmentTree { let size = n.next_power_of_two(); let bit = size.trailing_zeros() as usize; LazySegmentTree { size: size, bit: bit, a: vec![(R::e(), R::id()); 2 * size], } } pub fn build_by(z: &[R::T]) -> LazySegmentTree { let mut seg = LazySegmentTree::::new(z.len()); for (a, z) in seg.a[seg.size..].iter_mut().zip(z.iter()) { a.0 = z.clone(); } let a = &mut seg.a; for i in (1..seg.size).rev() { a[i].0 = R::fold(&a[2 * i].0, &a[2 * i + 1].0); } seg } fn apply(&mut self, x: usize, op: &R::E) { let node = &mut self.a[x]; node.0 = R::eval(&node.0, op); node.1 = R::merge(&node.1, op); } fn propagate(&mut self, x: usize) { let mut op = R::id(); std::mem::swap(&mut op, &mut self.a[x].1); self.apply(2 * x, &op); self.apply(2 * x + 1, &op); } fn propagate_range(&mut self, l: usize, r: usize) { let x = l + self.size; let y = r + self.size; let mut k = self.bit; while (x >> k) == (y >> k) { self.propagate(x >> k); k -= 1; } for i in ((x.trailing_zeros() as usize + 1)..=k).rev() { self.propagate(x >> i); } for i in ((y.trailing_zeros() as usize + 1)..=k).rev() { self.propagate(y >> i); } } fn save_range(&mut self, l: usize, r: usize) { let mut x = l + self.size; let mut y = r + self.size; let mut p = (x & 1) == 1; let mut q = (y & 1) == 1; x >>= 1; y >>= 1; while 0 < x && x < y { if p { self.a[x].0 = R::fold(&self.a[2 * x].0, &self.a[2 * x + 1].0); } if q { self.a[y].0 = R::fold(&self.a[2 * y].0, &self.a[2 * y + 1].0); } p |= (x & 1) == 1; q |= (y & 1) == 1; x >>= 1; y >>= 1; } while 0 < x { self.a[x].0 = R::fold(&self.a[2 * x].0, &self.a[2 * x + 1].0); x >>= 1; } } pub fn update(&mut self, l: usize, r: usize, op: R::E) { self.propagate_range(l, r); let mut x = l + self.size; let mut y = r + self.size; while x < y { if x & 1 == 1 { self.apply(x, &op); x += 1; } if y & 1 == 1 { y -= 1; self.apply(y, &op); } x >>= 1; y >>= 1; } self.save_range(l, r); } pub fn find(&mut self, l: usize, r: usize) -> R::T { self.propagate_range(l, r); let mut x = l + self.size; let mut y = r + self.size; let mut p = R::e(); let mut q = R::e(); while x < y { if x & 1 == 1 { p = R::fold(&p, &self.a[x].0); x += 1; } if y & 1 == 1 { y -= 1; q = R::fold(&self.a[y].0, &q); } x >>= 1; y >>= 1; } R::fold(&p, &q) } } // ---------- end Lazy Segment Tree ---------- // ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- use std::io::Write; struct R; impl TE for R { type T = i64; type E = i64; fn fold(l: &Self::T, r: &Self::T) -> Self::T { *l + *r } fn eval(x: &Self::T, f: &Self::E) -> Self::T { if *f >= 0 { *f } else { *x } } fn merge(g: &Self::E, h: &Self::E) -> Self::E { if *h == -1 { *g } else { *h } } fn e() -> Self::T { 0 } fn id() -> Self::E { -1 } } fn run() { input! { n: usize, e: [(usize, usize); n - 1], a: [i64; n], q: usize, ask: [usize; q], } let mut g = vec![vec![]; n]; for (a, b) in e { g[a].push(b); g[b].push(a); } let mut parent = vec![n; n]; let mut index = vec![n; n]; let mut range = vec![(n, n); n]; let mut topo = vec![0]; let mut s = vec![0; n]; for i in 0..n { let v = topo[i]; index[v] = i; s[i] = a[v]; range[v] = (topo.len(), topo.len() + g[v].len()); for u in g[v].clone() { let x = g[u].iter().position(|p| *p == v).unwrap(); g[u].remove(x); parent[u] = v; topo.push(u); } } let mut seg = LazySegmentTree::::build_by(&s); let out = std::io::stdout(); let mut out = std::io::BufWriter::new(out.lock()); for x in ask { let mut sum = 0; if parent[x] != n { let p = parent[x]; let (l, r) = range[p]; sum += seg.find(l, r); seg.update(l, r, 0); let k = index[p]; sum += seg.find(k, k + 1); seg.update(k, k + 1, 0); if parent[p] != n { let p = parent[p]; let k = index[p]; sum += seg.find(k, k + 1); seg.update(k, k + 1, 0); } } else { let k = index[x]; sum += seg.find(k, k + 1); seg.update(k, k + 1, 0); } if !g[x].is_empty() { let (l, r) = range[x]; sum += seg.find(l, r); seg.update(l, r, 0); let l = range[g[x][0]].0; let r = range[*g[x].last().unwrap()].1; if l < r { sum += seg.find(l, r); seg.update(l, r, 0); } } writeln!(out, "{}", sum).ok(); let k = index[x]; seg.update(k, k + 1, sum); } } fn main() { run(); }