#include #include struct bfs_euler_tour { int N; std::vector> G; std::vector in; std::vector out; std::vector para; std::vector dep; std::vector par; std::vector start; int cnt; int D; bfs_euler_tour(int N): N(N), G(N), in(N), out(N), para(N, -1), dep(N), par(N) {} void add_edge(int a, int b) { G[a].push_back(b); G[b].push_back(a); } void dfs(int v, int f, int depth) { D = std::max(D, depth); par[v] = f; dep[v] = depth; in[v] = cnt++; for(auto t: G[v]) { if(t == f) continue; dfs(t, v, depth + 1); } out[v] = cnt; } void build(int r) { cnt = 0; D = 0; dfs(r, -1, 0); D++; cnt = 0; std::vector que(N); int ql = 0; int qr = 0; que[qr++] = r; start.resize(D + 1); for(int d = 0; ql < qr; d++) { int r = qr; start[d] = cnt; while(ql < r) { int v = que[ql++]; para[cnt++] = v; for(auto t: G[v]) { if(para[t] == -1) { que[qr++] = t; } } } } start[D] = cnt; } int para_lower_bound(int l, int r, int i) { while(r - l > 1) { int m = (l + r) >> 1; if(i <= in[para[m]]) { r = m; } else { l = m; } } return r; } std::pair range(int v, int d) { if(dep[v] + d < D) { int l = start[dep[v] + d]; int r = start[dep[v] + d + 1]; return { para_lower_bound(l - 1, r, in[v]), para_lower_bound(l - 1, r, out[v]) }; } else { return { 0, 0 }; } } }; #include using namespace std; using i64 = long long; #define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++) #define all(x) x.begin(),x.end() template static inline std::vector ndvec(size_t&& n, T val) noexcept { return std::vector(n, std::forward(val)); } template static inline auto ndvec(size_t&& n, Tail&&... tail) noexcept { return std::vector(tail)...))>(n, ndvec(std::forward(tail)...)); } template struct chain { Cond cond; chain(Cond cond) : cond(cond) {} bool operator()(T& a, const T& b) const { if(cond(a, b)) { a = b; return true; } return false; } }; template chain make_chain(Cond cond) { return chain(cond); } #include #include #include using i64 = long long; struct lazy_segment_tree { using T = i64; using L = i64; static inline T t_ide() { return 0; } static inline L l_ide() { return 0; } static inline T ope(const T& a, const T& b) { return a + b; } static inline L lazy_ope(const L& a, const L& b) { return b; } static inline T effect(const T& t, const L& l) { return l; } int n, h; std::vector node; std::vector lazy; std::vector flag; lazy_segment_tree(int N) { n = 1; h = 1; while(n < N) n <<= 1, h++; node.resize(n << 1, t_ide()); lazy.resize(n << 1, l_ide()); flag.resize(n << 1, false); } lazy_segment_tree(const std::vector& init) { n = 1; h = 1; while(n < init.size()) n <<= 1, h++; node.resize(n << 1, t_ide()); lazy.resize(n << 1, l_ide()); flag.resize(n << 1, false); for(int i = 0;i < init.size();i++) node[i + n] = init[i]; for(int i = n; i --> 1;) node[i] = ope(node[(i << 1)], node[(i << 1) + 1]); } inline void eff(int k, L x) { if(k < n << 1) { lazy[k] = lazy_ope(lazy[k], x); flag[k] = true; } } inline T eval(int k) const { return flag[k] ? effect(node[k], lazy[k]) : node[k]; } inline void push(int k) { if(flag[k]) { node[k] = eval(k); eff(k << 1, lazy[k]); eff((k << 1) | 1, lazy[k]); lazy[k] = l_ide(); flag[k] = false; } } inline void infuse(int k) { k = k >> __builtin_ctz(k); while((k >>= 1)) node[k] = ope(eval(k << 1), eval((k << 1) + 1)); } inline void infiltrate(int k) { if(k == n << 1) return; int kc = __builtin_ctz(k); for(int i = h; i --> kc;) push(k >> i); } inline void infiltrate(int l, int r) { if(l == r) return; if(r == n << 1) infiltrate(l); else { int hh = h; int x = l ^ r; for(; !(x >> --hh);) push(l >> hh); int lc = __builtin_ctz(l); for(int i = hh + 1; i --> lc;) push(l >> i); int rc = __builtin_ctz(r); for(int i = hh + 1; i --> rc;) push(r >> i); } } void update(int a, int b, L x) { int l = a + n; int r = b + n; infiltrate(l, r); while(l < r) { if(l & 1) eff(l++, x); if(r & 1) eff(--r, x); l >>= 1; r >>= 1; } infuse(a + n); infuse(b + n); } T sum(int l, int r) { l += n; r += n; infiltrate(l, r); T lx = t_ide(); T rx = t_ide(); while(l < r) { if(l & 1) lx = ope(lx, eval(l++)); if(r & 1) rx = ope(eval(--r), rx); l >>= 1; r >>= 1; } return ope(lx, rx); } }; int main() { cin.tie(nullptr); std::ios::sync_with_stdio(false); int N; cin >> N; bfs_euler_tour eul(N); rep(i,0,N - 1) { int a, b; cin >> a >> b; eul.add_edge(a, b); } eul.build(0); vector A(N); vector init(N); rep(i,0,N) { cin >> A[i]; } rep(i,0,N) { init[i] = A[eul.para[i]]; } lazy_segment_tree seg(init); int Q; cin >> Q; i64 sum = 0; auto func = [&](int v, int d) { int l, r; std::tie(l, r) = eul.range(v, d); sum += seg.sum(l, r); seg.update(l, r, 0); }; while(Q--){ int v; cin >> v; sum = 0; if(eul.par[v] != -1) { int p = eul.par[v]; if(eul.par[p] != -1) { func(eul.par[p], 0); } func(p, 0); func(p, 1); } else { func(v, 0); } func(v, 1); func(v, 2); cout << sum << "\n"; seg.update(eul.para[v], eul.para[v] + 1, sum); } }