// includes {{{ #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #include // #include // #include // #include // }}} using namespace std; using ll = long long; // LazySegmentTree( size [, initial] ) // LazySegmentTree( ) /// --- LazySegmentTree {{{ /// #include #include #include #include template < class M_act > struct LazySegmentTree { public: using Monoid = typename M_act::Monoid; using X = typename Monoid::T; using M = typename M_act::M; private: size_t n; int h; vector< X > data; vector< M > lazy; vector< size_t > nodeLength; // call before use data[i] void eval(size_t i) { if(lazy[i] == M_act::identity()) return; data[i] = M_act::actInto(lazy[i], nodeLength[i], data[i]); if(i < n) { lazy[i * 2] = M_act::op(lazy[i], lazy[i * 2]); lazy[i * 2 + 1] = M_act::op(lazy[i], lazy[i * 2 + 1]); } lazy[i] = M_act::identity(); } // call before use seg[i] = data[i + n] void evalDown(size_t i) { i += n; for(int j = h - 1; j >= 0; j--) eval(i >> j); } // call after touch seg[i] = data[i + n] void propUp(size_t i) { i += n; while(i >>= 1) eval(i * 2), eval(i * 2 + 1), data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]); } public: LazySegmentTree() : n(0) {} LazySegmentTree(size_t n, X initial = Monoid::identity()) : n(n) { if(n > 0) { h = 1; while(1u << h < n) h++; data.resize(2 * n, initial); lazy.resize(2 * n, M_act::identity()); nodeLength.resize(2 * n, 1); for(size_t i = n - 1; i > 0; i--) // fill from deep data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]), nodeLength[i] = nodeLength[i * 2] + nodeLength[i * 2 + 1]; } } template < class InputIter, class = typename iterator_traits< InputIter >::value_type > LazySegmentTree(InputIter first, InputIter last) : LazySegmentTree(distance(first, last)) { if(n > 0) { copy(first, last, begin(data) + n); for(size_t i = n - 1; i > 0; i--) // fill from deep data[i] = Monoid::op(data[i * 2], data[i * 2 + 1]); } } LazySegmentTree(vector< X > v) : LazySegmentTree(v.begin(), v.end()) {} LazySegmentTree(initializer_list< X > v) : LazySegmentTree(v.begin(), v.end()) {} void act(int l, int r, const M &m) { if(l < 0) l = 0; if(l >= r) return; if(r > (int) n) r = n; evalDown(l); evalDown(r - 1); int tl = l, tr = r; for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) eval(l), lazy[l] = m, eval(l), l++; if(r & 1) --r, eval(r), lazy[r] = m, eval(r); } propUp(tl); propUp(tr - 1); } void set(size_t i, const X &x) { assert(i < n); evalDown(i); data[i + n] = x; propUp(i); } X get(size_t i) { assert(i < n); evalDown(i); return data[i + n]; } X fold(int l, int r) { if(l < 0) l = 0; if(l >= r) return Monoid::identity(); if(r > (int) n) r = n; evalDown(l); evalDown(r - 1); X tmpL = Monoid::identity(), tmpR = Monoid::identity(); for(l += n, r += n; l < r; l >>= 1, r >>= 1) { if(l & 1) eval(l), tmpL = Monoid::op(tmpL, data[l]), l++; if(r & 1) --r, eval(r), tmpR = Monoid::op(data[r], tmpR); } return Monoid::op(tmpL, tmpR); } int size() { return n; } inline void dum(int r = -1) { #ifdef DEBUG if(r < 0) r = n; DEBUG_OUT << "{"; for(int i = 0; i < min(r, (int) n); i++) DEBUG_OUT << (i ? ", " : "") << get(i); DEBUG_OUT << "}" << endl; #endif } }; /// }}}--- /// /// --- Monoid examples {{{ /// constexpr long long inf_monoid = 1e18 + 100; #include struct Nothing { using T = char; using Monoid = Nothing; using M = T; static constexpr T op(const T &, const T &) { return T(); } static constexpr T identity() { return T(); } template < class X > static constexpr X actInto(const M &, long long, const X &x) { return x; } }; template < class U = long long > struct RangeMin { using T = U; static T op(const T &a, const T &b) { return std::min< T >(a, b); } static constexpr T identity() { return T(inf_monoid); } }; template < class U = long long > struct RangeMax { using T = U; static T op(const T &a, const T &b) { return std::max< T >(a, b); } static constexpr T identity() { return T(-inf_monoid); } }; template < class U = long long > struct RangeSum { using T = U; static T op(const T &a, const T &b) { return a + b; } static constexpr T identity() { return T(0); } }; template < class U > struct RangeProd { using T = U; static T op(const T &a, const T &b) { return a * b; } static constexpr T identity() { return T(1); } }; template < class U = long long > struct RangeOr { using T = U; static T op(const T &a, const T &b) { return a | b; } static constexpr T identity() { return T(0); } }; #include template < class U = long long > struct RangeAnd { using T = U; static T op(const T &a, const T &b) { return a & b; } static constexpr T identity() { return T(-1); } }; template < size_t N > struct RangeAnd< std::bitset< N > > { using T = std::bitset< N >; static T op(const T &a, const T &b) { return a & b; } static constexpr T identity() { return std::bitset< N >().set(); } }; /// }}}--- /// /// --- M_act examples {{{ /// template < class U = long long, class V = U > struct RangeMinAdd { using X = U; using M = V; using Monoid = RangeMin< U >; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M &m, long long, const X &x) { return m + x; } }; template < class U = long long, class V = U > struct RangeMaxAdd { using X = U; using M = V; using Monoid = RangeMax< U >; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M &m, long long, const X &x) { return m + x; } }; template < class U = long long, class V = U > struct RangeMinSet { using M = U; using Monoid = RangeMin< U >; using X = typename Monoid::T; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeMaxSet { using M = U; using Monoid = RangeMax< U >; using X = typename Monoid::T; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeSumAdd { using X = U; using M = V; using Monoid = RangeSum< U >; static M op(const M &a, const M &b) { return a + b; } static constexpr M identity() { return 0; } static X actInto(const M &m, long long n, const X &x) { return m * n + x; } }; template < class U = long long, class V = U > struct RangeSumSet { using X = U; using M = V; using Monoid = RangeSum< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long n, const X &x) { return m == identity() ? x : m * n; } }; template < class U, class V = U > struct RangeProdMul { using X = U; using M = V; using Monoid = RangeProd< U >; static M mpow(M a, long long b) { X r(1); while(b) { if(b & 1) r = r * a; a = a * a; b >>= 1; } return r; } static M op(const M &a, const M &b) { return a * b; } static constexpr M identity() { return M(1); } static X actInto(const M &m, long long n, const X &x) { return x * mpow(m, n); } }; template < class U, class V = U > struct RangeProdSet { using X = U; using M = V; using Monoid = RangeProd< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return V::unused; } static X actInto(const M &m, long long n, const X &) { if(m == identity()) return; return RangeProdMul< U, V >::mpow(m, n); } }; template < class U = long long, class V = U > struct RangeOrSet { using X = U; using M = V; using Monoid = RangeOr< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeAndSet { using X = U; using M = V; using Monoid = RangeAnd< U >; static M op(const M &a, const M &b) { return a == identity() ? b : a; } static constexpr M identity() { return M(-inf_monoid); } static X actInto(const M &m, long long, const X &x) { return m == identity() ? x : m; } }; template < class U = long long, class V = U > struct RangeOr2 { using X = U; using M = V; using Monoid = RangeOr< U >; static M op(const M &a, const M &b) { return a | b; } static constexpr M identity() { return M(0); } static X actInto(const M &m, long long, const X &x) { return m | x; } }; template < class U = long long, class V = U > struct RangeAnd2 { using X = U; using M = V; using Monoid = RangeAnd< U >; static M op(const M &a, const M &b) { return a & b; } static constexpr M identity() { return M(-1); } static X actInto(const M &m, long long, const X &x) { return m & x; } }; template < class U, size_t N > struct RangeAnd2< U, std::bitset< N > > { using X = U; using M = std::bitset< N >; using Monoid = RangeAnd< U >; static M op(const M &a, const M &b) { return a & b; } static constexpr M identity() { return std::bitset< N >().set(); } static X actInto(const M &m, long long, const X &x) { return m & x; } }; /// }}}--- /// using Seg = LazySegmentTree< RangeSumSet<> >; const int N = 1e5 + 1; std::vector> g; int n; int dep[N], par[N]; int L[N], R[N]; int LL[N], RR[N]; int in[N]; int main() { std::ios::sync_with_stdio(false), std::cin.tie(0); cin >> n; g.resize(n); for(int i = 0; i < n - 1; i++) { int a, b; std::cin >> a >> b; g[a].emplace_back(b); g[b].emplace_back(a); } // bfs // like euler tour par[n] = n; { queue q; q.push(0); vector used(n); used[0] = 1; dep[0] = 0; par[0] = n; int id = 0; while(q.size()) { int i = q.front(); q.pop(); in[i] = id++; L[i] = -1; for(auto j : g[i]) if(used[j] == 0) { if(L[i] == -1) L[i] = j; R[i] = j; used[j] = 1; q.push(j); dep[j] = dep[i] + 1; par[j] = i; } } } Seg seg(n); for(int i = 0; i < n; i++) { int a; cin >> a; seg.set(in[i], a); LL[i] = -1; for(auto j : g[i]) if(par[i] != j) { if(LL[i] == -1) LL[i] = L[j]; if(L[j] != -1) RR[i] = R[j]; } } int q; cin >> q; for(int i = 0; i < q; i++) { int x; cin >> x; ll ans = 0; if(L[x] != -1) { // 1個下 ans += seg.fold(in[L[x]], in[R[x]] + 1); seg.act(in[L[x]], in[R[x]] + 1, 0); if(LL[x] != -1) { // 2個下 ans += seg.fold(in[LL[x]], in[RR[x]] + 1); seg.act(in[LL[x]], in[RR[x]] + 1, 0); } } if(par[x] != n) { // 親 ans += seg.get(in[par[x]]); seg.set(in[par[x]], 0); if(L[par[x]] != -1) { // 親 の 子すべて ans += seg.fold(in[L[par[x]]], in[R[par[x]]] + 1); seg.act(in[L[par[x]]], in[R[par[x]]] + 1, 0); } if(par[par[x]] != n) { // 親 の 親 ans += seg.get(in[par[par[x]]]); seg.set(in[par[par[x]]], 0); } } else { ans += seg.get(in[x]); seg.set(in[x], 0); } seg.set(in[x], ans); seg.dum(); cout << ans << "\n"; } return 0; }