// #pragma GCC optimize ("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target ("avx") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using Int = long long; template ostream &operator<<(ostream &os, const pair &a) { return os << "(" << a.first << ", " << a.second << ")"; }; template void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; } template void chmin(T &t, const T &f) { if (t > f) t = f; } template void chmax(T &t, const T &f) { if (t < f) t = f; } template struct SegmentTree { using OpTT = std::function; using OpSS = std::function; using OpST = std::function; const OpTT opTT; const OpSS opSS; const OpST opST; const T idT; const S idS; int n; vector ts; vector ss; SegmentTree(int n_, const OpTT opTT, const OpSS opSS, const OpST opST, const T &idT, const S &idS) : opTT(opTT), opSS(opSS), opST(opST), idT(idT), idS(idS) { for (n = 1; n < n_; n <<= 1) {} ts.assign(n << 1, idT); ss.assign(n << 1, idS); } T &at(int a) { return ts[n + a]; } void build() { for (int a = n; --a; ) ts[a] = opTT(ts[a << 1], ts[a << 1 | 1]); } T query(int a, int b, const S &s) { return query(1, 0, n, a, b, s); } private: T query(int u, int l, int r, int a, int b, const S &s) { if (a < l) a = l; if (b > r) b = r; if (a >= b) return idT; if (a == l && b == r) { ts[u] = opST(s, ts[u], r - l); ss[u] = opSS(s, ss[u]); return ts[u]; } const int uL = u << 1, uR = u << 1 | 1; const int mid = (l + r) >> 1; { ts[uL] = opST(ss[u], ts[uL], mid - l); ts[uR] = opST(ss[u], ts[uR], r - mid); ss[uL] = opSS(ss[u], ss[uL]); ss[uR] = opSS(ss[u], ss[uR]); ss[u] = idS; } const T resL = query(uL, l, mid, a, b, s); const T resR = query(uR, mid, r, a, b, s); ts[u] = opTT(ts[uL], ts[uR]); return opTT(resL, resR); } }; struct S { bool f; Int x; }; S opSS(const S &sa, const S &sb) { return sa.f ? sa : sb; } Int opST(const S &s, const Int &t, int sz) { return s.f ? (s.x * sz) : t; } constexpr S IdS{false, 0}; constexpr int MAX = 200010; int N; int U[MAX], V[MAX]; Int A[MAX]; int Q; int X[MAX]; vector G[MAX]; int par[MAX], dep[MAX]; int zeit, dis[MAX], fin[MAX]; pair, int> ps[MAX]; int ord[MAX]; pair ls[MAX], rs[MAX]; pair lls[MAX], rrs[MAX]; void dfs(int u, int p) { par[u] = p; dep[u] = (p == -1) ? 0 : (dep[p] + 1); dis[u] = zeit++; for (const int i : G[u]) { const int v = U[i] ^ V[i] ^ u; if (v != p) { dfs(v, u); } } fin[u] = zeit++; } int main() { for (; ~scanf("%d", &N); ) { for (int i = 0; i < N - 1; ++i) { scanf("%d%d", &U[i], &V[i]); } for (int u = 0; u < N; ++u) { scanf("%lld", &A[u]); } scanf("%d", &Q); for (int q = 0; q < Q; ++q) { scanf("%d", &X[q]); } for (int u = 0; u < N; ++u) { G[u].clear(); } for (int i = 0; i < N - 1; ++i) { G[U[i]].push_back(i); G[V[i]].push_back(i); } zeit = 0; dfs(0, -1); // cerr<<"dis = ";pv(dis,dis+N); // cerr<<"fin = ";pv(fin,fin+N); for (int u = 0; u < N; ++u) { ps[u] = make_pair(make_pair(dep[u], dis[u]), u); } sort(ps, ps + N); for (int j = 0; j < N; ++j) { ord[ps[j].second] = j; } fill(ls, ls + N, make_pair(N, -1)); fill(rs, rs + N, make_pair(-1, -1)); fill(lls, lls + N, make_pair(N, -1)); fill(rrs, rrs + N, make_pair(-1, -1)); for (int u = 0; u < N; ++u) { if (par[u] != -1) { chmin(ls[par[u]], make_pair(ord[u], u)); chmax(rs[par[u]], make_pair(ord[u], u)); if (par[par[u]] != -1) { chmin(lls[par[par[u]]], make_pair(ord[u], u)); chmax(rrs[par[par[u]]], make_pair(ord[u], u)); } } } // cerr<<"ps = ";pv(ps,ps+N); // cerr<<"ls = ";pv(ls,ls+N); // cerr<<"rs = ";pv(rs,rs+N); // cerr<<"lls = ";pv(lls,lls+N); // cerr<<"rrs = ";pv(rrs,rrs+N); SegmentTree seg(N, plus(), opSS, opST, 0, IdS); for (int u = 0; u < N; ++u) { seg.at(ord[u]) = A[u]; } seg.build(); for (int q = 0; q < Q; ++q) { const int u = X[q]; vector> intervals; if (par[u] != -1) { if (par[par[u]] != -1) { intervals.emplace_back(ord[par[par[u]]], ord[par[par[u]]]); } intervals.emplace_back(ord[par[u]], ord[par[u]]); intervals.emplace_back(ls[par[u]].first, rs[par[u]].first); } else { intervals.emplace_back(ord[u], ord[u]); } if (ls[u].second != -1) { intervals.emplace_back(ls[u].first, rs[u].first); if (lls[u].second != -1) { intervals.emplace_back(lls[u].first, rrs[u].first); } } Int ans = 0; for (const auto &interval : intervals) { ans += seg.query(interval.first, interval.second + 1, IdS); seg.query(interval.first, interval.second + 1, S{true, 0}); } seg.query(ord[u], ord[u] + 1, S{true, ans}); printf("%lld\n", ans); } } return 0; }