#include #include #include #include #include #define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() const int INF = 0x3f3f3f3f; const long long LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; /*-------------------------------------------------*/ template struct RSQandRUQ { RSQandRUQ(int sz, const Monoid &UNITY = 0) : UNITY(UNITY) { init(sz); dat.assign((n << 1) - 1, UNITY); } RSQandRUQ(const vector &a, const Monoid &UNITY = 0) : UNITY(UNITY) { int a_sz = a.size(); init(a_sz); dat.resize((n << 1) - 1); REP(i, a_sz) dat[n - 1 + i] = a[i]; for (int i = n - 2; i >= 0; --i) dat[i] = dat[(i << 1) + 1] + dat[(i << 1) + 2]; } void update(int a, int b, const Monoid &value) { update(a, b, value, 0, 0, n); } Monoid sum(int a, int b) { return sum(a, b, 0, 0, n); } Monoid operator[](const int idx) { return sum(idx, idx + 1); } int find(int a, int b, const Monoid &value) { return find(a, b, value, 0, 0, n); } private: int n = 1; const Monoid UNITY; vector dat, lazy; vector need_to_be_eval; void init(int sz) { while (n < sz) n <<= 1; lazy.assign((n << 1) - 1, UNITY); need_to_be_eval.assign((n << 1) - 1, false); } inline void evaluate(int node, int left, int right) { if (need_to_be_eval[node]) { dat[node] = (right - left) * lazy[node]; if (node < n - 1) { lazy[(node << 1) + 1] = lazy[(node << 1) + 2] = lazy[node]; need_to_be_eval[(node << 1) + 1] = need_to_be_eval[(node << 1) + 2] = true; } lazy[node] = UNITY; need_to_be_eval[node] = false; } } void update(int a, int b, const Monoid &value, int node, int left, int right) { evaluate(node, left, right); if (right <= a || b <= left) return; if (a <= left && right <= b) { lazy[node] = value; need_to_be_eval[node] = true; evaluate(node, left, right); } else { update(a, b, value, (node << 1) + 1, left, (left + right) >> 1); update(a, b, value, (node << 1) + 2, (left + right) >> 1, right); dat[node] = dat[(node << 1) + 1] + dat[(node << 1) + 2]; } } Monoid sum(int a, int b, int node, int left, int right) { evaluate(node, left, right); if (right <= a || b <= left) return UNITY; if (a <= left && right <= b) return dat[node]; return sum(a, b, (node << 1) + 1, left, (left + right) >> 1) + sum(a, b, (node << 1) + 2, (left + right) >> 1, right); } int find(int a, int b, const Monoid &value, int node, int left, int right) { evaluate(node, left, right); if (dat[node] < value || right <= a || b <= left) return -1; if (right - left == 1) return node - (n - 1); int res_l = find(a, b, value, (node << 1) + 1, left, (left + right) >> 1); if (res_l != -1) return res_l; return find(a, b, value, (node << 1) + 2, (left + right) >> 1, right); } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); // freopen("input.txt", "r", stdin); int n; cin >> n; vector > graph(n); REP(_, n - 1) { int u, v; cin >> u >> v; graph[u].emplace_back(v); graph[v].emplace_back(u); } vector idx(n, -1), par(n, -1), left(n, INF), right(n, -1); int now = 0; queue que; idx[0] = now++; que.emplace(0); while (!que.empty()) { int ver = que.front(); que.pop(); for (int e : graph[ver]) { if (idx[e] == -1) { idx[e] = now++; que.emplace(e); par[idx[e]] = idx[ver]; left[idx[ver]] = min(left[idx[ver]], idx[e]); right[idx[ver]] = max(right[idx[ver]], idx[e]); } } } vector child_left(n, INF), child_right(n, -1); REP(i, n) { for (int e : graph[i]) if (idx[e] != par[idx[i]]) { child_left[idx[i]] = min(child_left[idx[i]], left[idx[e]]); child_right[idx[i]] = max(child_right[idx[i]], right[idx[e]]); } } vector a(n); REP(i, n) cin >> a[i]; vector fairy(n); REP(i, n) fairy[idx[i]] = a[i]; RSQandRUQ rsq(fairy); int q; cin >> q; while (q--) { int x; cin >> x; x = idx[x]; long long ans = rsq[x]; rsq.update(x, x + 1, 0); if (par[x] != -1) { ans += rsq[par[x]]; rsq.update(par[x], par[x] + 1, 0); ans += rsq.sum(left[par[x]], right[par[x]] + 1); rsq.update(left[par[x]], right[par[x]] + 1, 0); if (par[par[x]] != -1) { ans += rsq[par[par[x]]]; rsq.update(par[par[x]], par[par[x]] + 1, 0); } } if (left[x] <= right[x]) { ans += rsq.sum(left[x], right[x] + 1); rsq.update(left[x], right[x] + 1, 0); if (child_left[x] <= child_right[x]) { ans += rsq.sum(child_left[x], child_right[x] + 1); rsq.update(child_left[x], child_right[x] + 1, 0); } } cout << ans << '\n'; rsq.update(x, x + 1, ans); } return 0; }