// #define DEBUGGING #include using namespace std; #define endl '\n' #define ALL(V) (V).begin(), (V).end() #define ALLR(V) (V).rbegin(), (V).rend() template using V = vector; template using VV = V>; using ll = int64_t; using ull = uint64_t; using PLL = pair; template const T& var_min(const T &t) { return t; } template const T& var_max(const T &t) { return t; } template const T& var_min(const T &t, const Tail&... tail) { return min(t, var_min(tail...)); } template const T& var_max(const T &t, const Tail&... tail) { return max(t, var_max(tail...)); } template void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); } template void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); } template const T& clamp(const T &t, const T &low, const T &high) { return max(low, min(high, t)); } template void chclamp(T &t, const T &low, const T &high) { t = clamp(t, low, high); } namespace init__ { struct InitIO { InitIO() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(30); } } init_io; } #ifdef DEBUGGING // #include "../debug/debug.cpp" #include "../../debug/debug.cpp" #else #define DEBUG(...) 0 #define DEBUG_SEPARATOR_LINE 0 #endif template T make_v(T init) { return init; } template auto make_v(T init, size_t s, Tail... tail) { #define rec make_v(init, tail...) return V(s, rec); #undef rec } template class LazySegmentTree { private: using Merge = function; using Apply = function; using Update = function; using CalcLazyValue = function; using Prop = function; size_t arr_size; T init_node; L init_lazy; vector node; vector lazy; vector lazy_flag; Merge merge_node; Apply apply_lazy_value; Update update_lazy_value; CalcLazyValue calc_lazy_value; Prop prop_lazy_value; public: LazySegmentTree(vector v, T init_node, L init_lazy, Merge merge_node, Apply apply_lazy_value, Update update_lazy_value, CalcLazyValue calc_lazy_value, Prop prop_lazy_value = [](L l) { return l; }) : init_node(init_node), init_lazy(init_lazy), merge_node(merge_node), apply_lazy_value(apply_lazy_value), update_lazy_value(update_lazy_value), calc_lazy_value(calc_lazy_value), prop_lazy_value(prop_lazy_value) { { arr_size = 1; while(arr_size < v.size()) arr_size *= 2; } node.resize(2 * arr_size - 1, init_node); lazy.resize(2 * arr_size - 1, init_lazy); lazy_flag.resize(2 * arr_size - 1, false); for(ll i = 0; i < v.size(); i++) node[i + arr_size - 1] = v[i]; for(ll i = arr_size - 2; 0 <= i; i--) node[i] = merge_node(node[i * 2 + 1], node[i * 2 + 2]); } void lazy_eval(ll pos, ll left, ll right) { if(!lazy_flag[pos]) return; node[pos] = apply_lazy_value(node[pos], lazy[pos]); lazy_flag[pos] = false; if(right - left > 1) { for(ll idx = 2 * pos + 1; idx <= 2 * pos + 2; idx++) { DEBUG(make_tuple(lazy[idx], prop_lazy_value(lazy[pos]), update_lazy_value(lazy[idx], prop_lazy_value(lazy[pos])))); lazy[idx] = update_lazy_value(lazy[idx], prop_lazy_value(lazy[pos])); lazy_flag[idx] = true; } } lazy[pos] = init_lazy; } void update_query(ll left, ll right, L val, ll pos = 0, ll node_left = 0, ll node_right = -1) { if(node_right < 0) node_right = arr_size; lazy_eval(pos, node_left, node_right); if(right <= node_left || node_right <= left) return; if(left <= node_left && node_right <= right) { lazy[pos] = calc_lazy_value(node_left, node_right, val); DEBUG(make_tuple(left, right, node_left, node_right, lazy[pos])); lazy_flag[pos] = true; lazy_eval(pos, node_left, node_right); } else { ll mid = (node_left + node_right) / 2; update_query(left, right, val, 2 * pos + 1, node_left, mid); update_query(left, right, val, 2 * pos + 2, mid, node_right); node[pos] = merge_node(node[2 * pos + 1], node[2 * pos + 2]); } } T get_query(ll left, ll right, ll pos = 0, ll node_left = 0, ll node_right = -1) { if(node_right < 0) node_right = arr_size; lazy_eval(pos, node_left, node_right); if(node_right <= left || right <= node_left) return init_node; if(left <= node_left && node_right <= right) return node[pos]; ll mid = (node_left + node_right) / 2; return merge_node(get_query(left, right, 2 * pos + 1, node_left, mid), get_query(left, right, 2 * pos + 2, mid, node_right)); } }; // cur, par, par-par using TLL = tuple; const ll inf = 5e15; int main() { ll N; cin >> N; VV edges(N); for(ll i = 1; i < N; i++) { ll u, v; cin >> u >> v; edges[u].emplace_back(v); edges[v].emplace_back(u); } for(auto &&v : edges) sort(ALL(v)); V A(N); for(auto &&ele : A) cin >> ele; V one(N, PLL(inf, -inf)), two(N, PLL(inf, -inf)); V nodes(N), rnodes(N); V parents(N, PLL(-1, -1)); { auto update_pll = [&](PLL &p, ll v) { ll a, b; tie(a, b) = p; chmin(a, v); chmax(b, v); p = PLL(a, b); }; V used(N); queue que; que.emplace(0, -1, -1); used[0] = true; ll node_idx = 0; while(que.size()) { ll cur, par1, par2; tie(cur, par1, par2) = que.front(); DEBUG(que.front()); que.pop(); nodes[node_idx] = cur; rnodes[cur] = node_idx; if(par1 != -1) { update_pll(one[par1], node_idx); parents[cur].first = par1; } if(par2 != -1) { update_pll(two[par2], node_idx); parents[cur].second = par2; } for(ll nxt : edges[cur]) { if(used[nxt]) continue; used[nxt] = true; que.emplace(nxt, cur, par1); } node_idx++; } } { V tmp = move(A); A.resize(N); for(ll i = 0; i < N; i++) A[i] = tmp[nodes[i]]; A = move(tmp); } DEBUG(nodes, rnodes, A); LazySegmentTree lst(A, 0, 0, [&](ll a, ll b) { return a + b; }, [&](ll a, ll b) { return b; }, [&](ll a, ll b) { return b; }, [&](ll l, ll r, ll a) { return a; }); ll Q; cin >> Q; while(Q--) { ll x; cin >> x; ll cur = lst.get_query(rnodes[x], rnodes[x] + 1); lst.update_query(rnodes[x], rnodes[x] + 1, 0); DEBUG(rnodes[x]); DEBUG(lst.get_query(rnodes[x], rnodes[x] + 1)); PLL onep = one[x], twop = two[x]; ll par1, par2; tie(par1, par2) = parents[x]; auto update = [&](const PLL &range) { ll l, r; tie(l, r) = range; if(l < 0 || r < 0) return; DEBUG(range); l = rnodes[l]; r = rnodes[r] + 1; ll sum = lst.get_query(l, r); DEBUG(sum); cur += sum; lst.update_query(l, r, 0); }; PLL ranges[] = { onep, twop, PLL(par1, par1), PLL(par2, par2) }; // DEBUG(make_tuple(ranges[0], ranges[1], ranges[2], ranges[3])); for(ll i = 0; i < 4; i++) update(ranges[i]); if(edges[x][0] == 0) update(one[0]); lst.update_query(rnodes[x], rnodes[x] + 1, cur); cout << cur << endl; } return 0; }