#line 2 "/home/maspy/library/my_template.hpp" #include using namespace std; using ll = long long; using ll8 = __int128; using ld = long double; using pi = pair; using vi = vector; using uint = unsigned int; using ull = unsigned long long; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; template using pq = priority_queue; template using pqg = priority_queue, greater>; #define vec(type, name, ...) vector name(__VA_ARGS__) #define VEC(type, name, size) \ vector name(size); \ IN(name) #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define VV(type, name, h, w) \ vector> name(h, vector(w)); \ IN(name) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) #define FOR(i, n) for (ll i = 0; (i) < (ll)(n); ++(i)) #define FOR3(i, m, n) for (ll i = (m); (i) < (ll)(n); ++(i)) #define FOR_R(i, n) for (ll i = (ll)(n)-1; (i) >= 0; --(i)) #define FOR3_R(i, m, n) for (ll i = (ll)(n)-1; (i) >= (ll)(m); --(i)) #define FOR_subset(t, s) for (ll t = s; t >= 0; t = (t == 0 ? -1 : (t - 1) & s)) #define all(x) x.begin(), x.end() #define len(x) ll(x.size()) #define elif else if #define eb emplace_back #define mp make_pair #define mt make_tuple #define fi first #define se second int popcnt(int x) { return __builtin_popcount(x); } int popcnt(uint x) { return __builtin_popcount(x); } int popcnt(ll x) { return __builtin_popcountll(x); } int popcnt(ull x) { return __builtin_popcountll(x); } // (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2) int topbit(int x) { return 31 - __builtin_clz(x); } int topbit(uint x) { return 31 - __builtin_clz(x); } int topbit(ll x) { return 63 - __builtin_clzll(x); } int topbit(ull x) { return 63 - __builtin_clzll(x); } // (0, 1, 2, 3, 4) -> (32 or 64, 0, 1, 0, 2) int lowbit(int x) { return 31 - __builtin_clz(x); } int lowbit(uint x) { return 31 - __builtin_clz(x); } int lowbit(ll x) { return 63 - __builtin_clzll(x); } int lowbit(ull x) { return 63 - __builtin_clzll(x); } ll ceil(ll x, ll y) { return (x > 0 ? (x + y - 1) / y : x / y); } ll floor(ll x, ll y) { return (x > 0 ? x / y : (x - y + 1) / y); } pi divmod(ll x, ll y) { ll q = floor(x, y); return {q, x - q * y}; } #define INT(...) \ int __VA_ARGS__; \ IN(__VA_ARGS__) #define LL(...) \ ll __VA_ARGS__; \ IN(__VA_ARGS__) #define STR(...) \ string __VA_ARGS__; \ IN(__VA_ARGS__) #define CHR(...) \ char __VA_ARGS__; \ IN(__VA_ARGS__) #define DBL(...) \ long double __VA_ARGS__; \ IN(__VA_ARGS__) void scan(int &a) { cin >> a; } void scan(long long &a) { cin >> a; } void scan(char &a) { cin >> a; } void scan(double &a) { cin >> a; } void scan(long double &a) { cin >> a; } void scan(string &a) { cin >> a; } template void scan(pair &p) { scan(p.first), scan(p.second); } template void scan(tuple &p) { scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p)); } template void scan(tuple &p) { scan(get<0>(p)), scan(get<1>(p)), scan(get<2>(p)), scan(get<3>(p)); } template void scan(vector &a) { for (auto &i: a) scan(i); } template void scan(T &a) { cin >> a; } void IN() {} template void IN(Head &head, Tail &... tail) { scan(head); IN(tail...); } vi s_to_vi(string S, char first_char = 'a') { vi A(S.size()); FOR(i, S.size()) { A[i] = S[i] - first_char; } return A; } template ostream &operator<<(ostream &os, const pair &A) { os << A.fi << " " << A.se; return os; } template ostream &operator<<(ostream &os, const tuple &t) { os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t); return os; } template ostream &operator<<(ostream &os, const tuple &t) { os << get<0>(t) << " " << get<1>(t) << " " << get<2>(t) << " " << get<3>(t); return os; } template ostream &operator<<(ostream &os, const vector &A) { for (size_t i = 0; i < A.size(); i++) { if (i) os << " "; os << A[i]; } return os; } void print() { cout << "\n"; } template void print(Head &&head, Tail &&... tail) { cout << head; if (sizeof...(Tail)) cout << " "; print(forward(tail)...); } void YES(bool t = 1) { print(t ? "YES" : "NO"); } void NO(bool t = 1) { YES(!t); } void Yes(bool t = 1) { print(t ? "Yes" : "No"); } void No(bool t = 1) { Yes(!t); } void yes(bool t = 1) { print(t ? "yes" : "no"); } void no(bool t = 1) { yes(!t); } template vector cumsum(vector &A) { int N = A.size(); vector B(N + 1); B[0] = T(0); FOR(i, N) { B[i + 1] = B[i] + A[i]; } return B; } vc bin_count(vi &A, int size) { vc C(size); for (auto &x: A) { ++C[x]; } return C; } template vector argsort(vector &A) { vector ids(A.size()); iota(all(ids), 0); sort(all(ids), [&](int i, int j) { return A[i] < A[j] || (A[i] == A[j] && i < j); }); return ids; } ll binary_search(function check, ll ok, ll ng) { assert(check(ok)); while (abs(ok - ng) > 1) { auto x = (ng + ok) / 2; if (check(x)) ok = x; else ng = x; } return ok; } template inline bool chmax(T &a, const S &b) { return (a < b ? a = b, 1 : 0); } template inline bool chmin(T &a, const S &b) { return (a > b ? a = b, 1 : 0); } #define SUM(v) accumulate(all(v), 0LL) #define MIN(v) *min_element(all(v)) #define MAX(v) *max_element(all(v)) #define LB(c, x) distance((c).begin(), lower_bound(all(c), (x))) #define UB(c, x) distance((c).begin(), upper_bound(all(c), (x))) #define UNIQUE(x) sort(all(x)), x.erase(unique(all(x)), x.end()) #line 2 "/home/maspy/library/graph/base.hpp" // frm, to, cap, cost template using Edge = tuple; template struct Graph { int N, M; using cost_type = T; using edge_type = Edge; vector edges; vector indptr; vector csr_edges; bool prepared; class OutgoingEdges { public: OutgoingEdges(const Graph* G, int l, int r) : G(G), l(l), r(r) {} const edge_type* begin() const { if (l == r) { return 0; } return &G->csr_edges[l]; } const edge_type* end() const { if (l == r) { return 0; } return &G->csr_edges[r]; } private: int l, r; const Graph* G; }; bool is_prepared() { return prepared; } constexpr bool is_directed() { return directed; } Graph() {} Graph(int N) : N(N), M(0), prepared(0) {} void add(int frm, int to, T cost = 1, int i = -1) { assert(!prepared); if (i == -1) i = M; auto e = edge_type({frm, to, cost, i}); edges.eb(e); ++M; } void prepare() { assert(!prepared); prepared = true; indptr.assign(N + 1, 0); for (auto&& [frm, to, cost, id]: edges) { indptr[frm + 1]++; if (!directed) indptr[to + 1]++; } FOR(v, N) indptr[v + 1] += indptr[v]; auto counter = indptr; csr_edges.resize(indptr.back() + 1); for (auto&& [frm, to, cost, id]: edges) { csr_edges[counter[frm]++] = {frm, to, cost, id}; if (!directed) csr_edges[counter[to]++] = {to, frm, cost, id}; } } OutgoingEdges operator[](int v) const { assert(prepared); return {this, indptr[v], indptr[v + 1]}; } void debug() { print("Graph"); if (!prepared) { print("frm to cost id"); for (auto&& e: edges) print(e); } else { print("indptr", indptr); print("frm to cost id"); FOR(v, N) for (auto&& e: (*this)[v]) print(e); } } int size() { return N; } }; #line 2 "/home/maspy/library/graph/bfsnumbering.hpp" template struct BFSNumbering { Graph& G; int root; vector V; vector ID; vector depth; vector parent; vector LID, RID; vector LID_seq; vector dep_ids; int cnt; BFSNumbering(Graph& G, int root = 0) : G(G), root(root), cnt(0) { build(); } void bfs() { deque que = {root}; while (!que.empty()) { int v = que.front(); que.pop_front(); ID[v] = V.size(); V.eb(v); for(auto&& [frm,to,cost,id] : G[v]) { if (to == parent[v]) continue; que.emplace_back(to); parent[to] = v; depth[to] = depth[v] + 1; } } } void dfs(int v) { LID[v] = cnt++; for(auto&& [frm,to,cost,id] : G[v]) { if (to == parent[v]) continue; dfs(to); } RID[v] = cnt; } void build() { int N = G.N; V.reserve(N); parent.assign(N, -1); ID.assign(N, 0); LID.assign(N, 0); RID.assign(N, 0); depth.assign(N, 0); bfs(); dfs(root); int D = MAX(depth); dep_ids.resize(D + 2); FOR(v, N) dep_ids[depth[v] + 1]++; FOR(d, D + 1) dep_ids[d + 1] += dep_ids[d]; LID_seq.reserve(N); FOR(i, N) LID_seq.eb(LID[V[i]]); } int bs(int L, int R, int x) { while (L + 1 < R) { int M = (L + R) / 2; if (LID_seq[M] >= x) R = M; else L = M; } return R; } pair calc_range(int v, int dep) { assert(dep >= depth[v]); if (dep >= len(dep_ids) - 1) return {0, 0}; int l = LID[v], r = RID[v]; int L = dep_ids[dep], R = dep_ids[dep + 1]; int a = bs(L - 1, R, l); int b = bs(L - 1, R, r); return {a, b}; } }; #line 2 "/home/maspy/library/ds/lazysegtree.hpp" template struct LazySegTree { using Monoid_X = typename Lazy::X_structure; using Monoid_A = typename Lazy::A_structure; using X = typename Monoid_X::value_type; using A = typename Monoid_A::value_type; int n, log, size; vc dat; vc laz; LazySegTree() : LazySegTree(0) {} LazySegTree(int n) : LazySegTree(vc(n, Monoid_X::unit)) {} LazySegTree(vc v) : n(len(v)) { log = 1; while ((1 << log) < n) ++log; size = 1 << log; dat.assign(size << 1, Monoid_X::unit); laz.assign(size, Monoid_A::unit); FOR(i, n) dat[size + i] = v[i]; FOR3_R(i, 1, size) update(i); } void update(int k) { dat[k] = Monoid_X::op(dat[2 * k], dat[2 * k + 1]); } void all_apply(int k, A a) { dat[k] = Lazy::act(dat[k], a); if (k < size) laz[k] = Monoid_A::op(laz[k], a); } void push(int k) { all_apply(2 * k, laz[k]); all_apply(2 * k + 1, laz[k]); laz[k] = Monoid_A::unit; } void set(int p, X x) { assert(0 <= p && p < n); p += size; for (int i = log; i >= 1; i--) push(p >> i); dat[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } X get(int p) { assert(0 <= p && p < n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return dat[p]; } vc get_all() { FOR(i, size) push(i); return {dat.begin() + size, dat.begin() + size + n}; } X prod(int l, int r) { assert(0 <= l && l <= r && r <= n); if (l == r) return Monoid_X::unit; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } X xl = Monoid_X::unit, xr = Monoid_X::unit; while (l < r) { if (l & 1) xl = Monoid_X::op(xl, dat[l++]); if (r & 1) xr = Monoid_X::op(dat[--r], xr); l >>= 1; r >>= 1; } return Monoid_X::op(xl, xr); } X all_prod() { return dat[1]; } void apply(int p, A a) { assert(0 <= p && p < n); p += size; if (!Monoid_A::commute) for (int i = log; i >= 1; i--) push(p >> i); dat[p] = Lazy::act(dat[p], a); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, A a) { assert(0 <= l && l <= r && r <= n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, a); if (r & 1) all_apply(--r, a); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(C& check, int l) { assert(0 <= l && l <= n); assert(check(Monoid_X::unit)); if (l == n) return n; l += size; for (int i = log; i >= 1; i--) push(l >> i); X sm = Monoid_X::unit; do { while (l % 2 == 0) l >>= 1; if (!check(Monoid_X::op(sm, dat[l]))) { while (l < size) { push(l); l = (2 * l); if (check(Monoid_X::op(sm, dat[l]))) { sm = Monoid_X::op(sm, dat[l]); l++; } } return l - size; } sm = Monoid_X::op(sm, dat[l]); l++; } while ((l & -l) != l); return n; } template int min_left(C& check, int r) { assert(0 <= r && r <= n); assert(check(Monoid_X::unit)); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); X sm = Monoid_X::unit; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!check(Monoid_X::op(dat[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (check(Monoid_X::op(dat[r], sm))) { sm = Monoid_X::op(dat[r], sm); r--; } } return r + 1 - size; } sm = Monoid_X::op(dat[r], sm); } while ((r & -r) != r); return 0; } void debug() { print("lazysegtree getall:", get_all()); } }; #line 1 "/home/maspy/library/algebra/addgroup.hpp" template struct AddGroup { using value_type = X; static constexpr X op(const X &x, const X &y) noexcept { return x + y; } static constexpr X inverse(const X &x) noexcept { return -x; } static constexpr X unit = ZERO; static constexpr bool commute = true; }; #line 1 "/home/maspy/library/algebra/mulgroup.hpp" template struct MulGroup { using value_type = X; static constexpr X op(const X &x, const X &y) noexcept { return x * y; } static constexpr X inverse(const X &x) noexcept { return X(1) / x; } static constexpr X unit = ONE; static constexpr bool commute = true; }; #line 6 "main.cpp" template struct Add_Mul { using MX = AddGroup; using MA = MulGroup; using X_structure = MX; using A_structure = MA; using X = typename MX::value_type; using A = typename MA::value_type; static constexpr X act(const X &x, const A &a) { return x * a; } }; void solve() { LL(N); Graph G(N); FOR(_, N - 1) { LL(a, b); G.add(a, b); } G.prepare(); VEC(ll, A, N); BFSNumbering BFS(G); auto &ID = BFS.ID; using Lazy = Add_Mul; LazySegTree seg(N); FOR(v, N) seg.set(ID[v], A[v]); LL(Q); FOR(_, Q) { LL(v); ll p = BFS.parent[v]; ll pp = (p == -1 ? -1 : BFS.parent[p]); ll x = 0; if (pp >= 0) x += seg.get(ID[pp]), seg.set(ID[pp], 0); if (p >= 0) { x += seg.get(ID[p]), seg.set(ID[p], 0); auto [l, r] = BFS.calc_range(p, 1); x += seg.prod(l, r), seg.apply(l, r, 0); } FOR(d, 3) { auto [l, r] = BFS.calc_range(v, BFS.depth[v] + d); x += seg.prod(l, r), seg.apply(l, r, 0); } print(x); seg.set(ID[v], x); } } signed main() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << setprecision(15); ll T = 1; // LL(T); FOR(_, T) solve(); return 0; }