#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } constexpr long long MAX = 5100000; constexpr long long INF = 1LL << 60; constexpr int inf = 1 << 28; constexpr long long mod = 1000000007LL; //constexpr long long mod = 998244353LL; using namespace std; typedef unsigned long long ull; typedef long long ll; template< typename Monoid, typename OperatorMonoid = Monoid > struct LazySegmentTree { using F = function< Monoid(Monoid, Monoid) >; using G = function< Monoid(Monoid, OperatorMonoid) >; using H = function< OperatorMonoid(OperatorMonoid, OperatorMonoid) >; int sz, height; vector< Monoid > data; vector< OperatorMonoid > lazy; const F f; const G g; const H h; const Monoid M1; const OperatorMonoid OM0; LazySegmentTree(int n, const F f, const G g, const H h, const Monoid& M1, const OperatorMonoid OM0) : f(f), g(g), h(h), M1(M1), OM0(OM0) { sz = 1; height = 0; while (sz < n) sz <<= 1, height++; data.assign(2 * sz, M1); lazy.assign(2 * sz, OM0); } void set(int k, const Monoid& x) { data[k + sz] = x; } void build() { for (int k = sz - 1; k > 0; k--) { data[k] = f(data[2 * k + 0], data[2 * k + 1]); } } inline void propagate(int k) { if (lazy[k] != OM0) { lazy[2 * k + 0] = h(lazy[2 * k + 0], lazy[k]); lazy[2 * k + 1] = h(lazy[2 * k + 1], lazy[k]); data[k] = reflect(k); lazy[k] = OM0; } } inline Monoid reflect(int k) { return lazy[k] == OM0 ? data[k] : g(data[k], lazy[k]); } inline void recalc(int k) { while (k >>= 1) data[k] = f(reflect(2 * k + 0), reflect(2 * k + 1)); } inline void thrust(int k) { for (int i = height; i > 0; i--) propagate(k >> i); } void update(int a, int b, const OperatorMonoid& x) { thrust(a += sz); thrust(b += sz - 1); for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) lazy[l] = h(lazy[l], x), ++l; if (r & 1) --r, lazy[r] = h(lazy[r], x); } recalc(a); recalc(b); } Monoid query(int a, int b) { thrust(a += sz); thrust(b += sz - 1); Monoid L = M1, R = M1; for (int l = a, r = b + 1; l < r; l >>= 1, r >>= 1) { if (l & 1) L = f(L, reflect(l++)); if (r & 1) R = f(reflect(--r), R); } return f(L, R); } Monoid operator[](const int& k) { return query(k, k + 1); } template< typename C > int find_subtree(int a, const C& check, Monoid& M, bool type) { while (a < sz) { propagate(a); Monoid nxt = type ? f(reflect(2 * a + type), M) : f(M, reflect(2 * a + type)); if (check(nxt)) a = 2 * a + type; else M = nxt, a = 2 * a + 1 - type; } return a - sz; } template< typename C > int find_first(int a, const C& check) { Monoid L = M1; if (a <= 0) { if (check(f(L, reflect(1)))) return find_subtree(1, check, L, false); return -1; } thrust(a + sz); int b = sz; for (a += sz, b += sz; a < b; a >>= 1, b >>= 1) { if (a & 1) { Monoid nxt = f(L, reflect(a)); if (check(nxt)) return find_subtree(a, check, L, false); L = nxt; ++a; } } return -1; } template< typename C > int find_last(int b, const C& check) { Monoid R = M1; if (b >= sz) { if (check(f(reflect(1), R))) return find_subtree(1, check, R, true); return -1; } thrust(b + sz - 1); int a = sz; for (b += sz; a < b; a >>= 1, b >>= 1) { if (b & 1) { Monoid nxt = f(reflect(--b), R); if (check(nxt)) return find_subtree(b, check, R, true); R = nxt; } } return -1; } }; pair f1(pair a, pair b) { return { a.first + b.first, a.second + b.second }; } pair f2(pair a, ll b) { if (b == INF) return a; else return { b * a.second, a.second }; } ll f3(ll a, ll b) { if (b == INF) return a; else return b; } vector g[100005]; int main() { /* cin.tie(nullptr); ios::sync_with_stdio(false); */ int n; scanf("%d", &n); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); g[u].push_back(v); g[v].push_back(u); } vector idx(n, -1), par(n, -1); vector L1(n, -1), R1(n, -1), L2(n, -1), R2(n, -1); queue q; q.push(0); idx[0] = 0; int now = 1; while (!q.empty()) { int cur = q.front(); q.pop(); for (auto next : g[cur]) { if (idx[next] != -1) continue; idx[next] = now++; par[next] = cur; if (L1[cur] == -1) L1[cur] = idx[next]; R1[cur] = idx[next]; int p = par[cur]; if (p != -1) { if (L2[p] == -1) L2[p] = idx[next]; R2[p] = idx[next]; } q.push(next); } } LazySegmentTree, ll> lsg(n, f1, f2, f3, { 0,0 }, INF); for (int i = 0; i < n; i++) { int a; scanf("%d", &a); lsg.set(idx[i], { a,1 }); } lsg.build(); int Q; scanf("%d", &Q); while (Q--) { int x; scanf("%d", &x); ll res = 0; res += lsg.query(idx[x], idx[x] + 1).first; lsg.update(idx[x], idx[x] + 1, 0); if (L1[x] != -1) { res += lsg.query(L1[x], R1[x] + 1).first; lsg.update(L1[x], R1[x] + 1, 0); } if (L2[x] != -1) { res += lsg.query(L2[x], R2[x] + 1).first; lsg.update(L2[x], R2[x] + 1, 0); } if (par[x] != -1) { int p = idx[par[x]]; res += lsg.query(p, p + 1).first; lsg.update(p, p + 1, 0); if (par[par[x]] != -1) { int pp = idx[par[par[x]]]; res += lsg.query(pp, pp + 1).first; lsg.update(pp, pp + 1, 0); } if (L1[par[x]] != -1) { res += lsg.query(L1[par[x]], R1[par[x]] + 1).first; lsg.update(L1[par[x]], R1[par[x]] + 1, 0); } } printf("%lld\n", res); lsg.update(idx[x], idx[x] + 1, res); } return 0; /* おまじないを使ったらscanfとprintf関連注意!!!!!!!!!!!! */ }