#include"bits/stdc++.h" using namespace std; #define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++) #define rep(i,n) REP((i),0,(n)) using ll = long long; constexpr ll INF = 1ll << 60; template class LazySegmentTree { private: using F = function; using G = function; using H = function; int sz; // 対応する配列の幅 vector data; vector lazy; const F f; // 2区間マージ演算(data-data-ボトムアップマージ) const G g; // 要素,作用素マージ演算(lazy->data同位置変換時の、(data,lazy,len)の計算) const H h; // 作用素マージ演算 (query->lazyトップダウン伝搬時の、(lazy,query_value)の計算) const Monoid M1; // モノイド単位元 (data単位元) const OperatorMonoid OM0; // 作用素単位元 (lazy単位元) void propagate(int idx, int len) { // 幅lenのlazy[idx]が存在するとき、値を下に流す if (lazy[idx] != OM0) { if (idx < sz) { lazy[(idx << 1) | 0] = h(lazy[(idx << 1) | 0], lazy[idx]); lazy[(idx << 1) | 1] = h(lazy[(idx << 1) | 1], lazy[idx]); } data[idx] = g(data[idx], lazy[idx], len); lazy[idx] = OM0; } } Monoid update_impl(int a, int b, const OperatorMonoid& val, int idx, int l, int r) { propagate(idx, r - l); if (r <= a || b <= l)return data[idx]; else if (a <= l && r <= b) { lazy[idx] = h(lazy[idx], val); propagate(idx, r - l); return data[idx]; } else return data[idx] = f( update_impl(a, b, val, (idx << 1) | 0, l, (l + r) >> 1), update_impl(a, b, val, (idx << 1) | 1, (l + r) >> 1, r) ); } Monoid query_impl(int a, int b, int idx, int l, int r) { propagate(idx, r - l); if (r <= a || b <= l)return M1; else if (a <= l && r <= b)return data[idx]; else return f( query_impl(a, b, (idx << 1) | 0, l, (l + r) >> 1), query_impl(a, b, (idx << 1) | 1, (l + r) >> 1, r) ); } public: // init忘れに注意 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; while (sz < n)sz <<= 1; data.assign(2 * sz, M1); lazy.assign(2 * sz, OM0); } void build(const vector& vals) { rep(idx, vals.size())data[idx + sz] = vals[idx]; for (int idx = sz - 1; idx > 0; idx--) { data[idx] = f(data[(idx << 1) | 0], data[(idx << 1) | 1]); } } Monoid update(int a, int b, const OperatorMonoid& val) { return update_impl(a, b, val, 1, 0, sz); } Monoid query(int a, int b) { return query_impl(a, b, 1, 0, sz); } Monoid operator[](const int& idx) { return query(idx, idx + 1); } }; int main() { ll N; cin >> N; vector> g(N); rep(i, N - 1) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } vector euler(N, -1), par(N, -1); vector> child(N), grand(N); { queue> st; st.push({ -1,0 }); ll cnt = 0; while (!st.empty()) { ll pari, nowi; tie(pari, nowi) = st.front(); st.pop(); euler[nowi] = cnt++; par[nowi] = pari; for (ll next : g[nowi]) if (next != pari) { st.push({ nowi,next }); } } rep(now, N) { ll minv = INF, maxv = -INF; for (ll next : g[now])if (next != par[now]) { minv = min(minv, euler[next]); maxv = max(maxv, euler[next]); } child[now] = { minv, maxv }; } rep(now, N) { ll minv = INF, maxv = -INF; for (ll next : g[now])if (next != par[now]) { minv = min(minv, child[next].first); maxv = max(maxv, child[next].second); } grand[now] = { minv,maxv }; } } auto f = [](ll vl, ll vr) { return (vl == INF ? 0 : vl) + (vr == INF ? 0 : vr); }; auto gf = [](ll data, ll lazy, int len) { return lazy == INF ? data : lazy * len; }; auto h = [](ll lazy, ll query) { return query == INF ? lazy : query; }; vector A(N); rep(i, N) { ll a; cin >> a; A[euler[i]] = a; } LazySegmentTree lst(N, f, gf, h, INF, INF); lst.build(A); int Q; cin >> Q; ll l, r; while (Q--) { int x; cin >> x; ll res = 0; if (par[x] != -1) { int idx = euler[par[x]]; res += lst[idx]; lst.update(idx, idx + 1, 0); tie(l, r) = child[par[x]]; res += lst.query(l, r + 1); lst.update(l, r + 1, 0); if (par[par[x]] != -1) { idx = euler[par[par[x]]]; res += lst[idx]; lst.update(idx, idx + 1, 0); } } else { int idx = euler[x]; res += lst[idx]; lst.update(idx, idx + 1, 0); } if (child[x].first != INF) { tie(l, r) = child[x]; res += lst.query(l, r + 1); lst.update(l, r + 1, 0); } if (grand[x].first != INF) { tie(l, r) = grand[x]; res += lst.query(l, r + 1); lst.update(l, r + 1, 0); } cout << res << endl; int now = euler[x]; lst.update(now, now + 1, res); } return 0; }