#include #include #include #define llint long long #define inf 1e18 using namespace std; // range-add, range-min query struct SegTree{ int size; vector seg, delay; SegTree(){} SegTree(int size){ this->size = size; seg.resize(1<<(size+1)); delay.resize(1<<(size+1)); } void init() { for(int i = 0; i < (1<<(size+1)); i++){ seg[i] = 0; delay[i] = -1; } } void eval(int l, int r, int k) { if(delay[k] >= 0){ seg[k] = delay[k] * (r-l+1); //総和クエリのときは区間幅を乗じる必要がある if(l < r){ delay[k*2] = delay[k]; delay[k*2+1] = delay[k]; } delay[k] = -1; } } void update(int i, llint val) { i += (1 << size); seg[i] = val; while(i > 1){ i /= 2; seg[i] = (seg[i*2] + seg[i*2+1]); } } void add(int a, int b, int k, int l, int r, llint val) { eval(l, r, k); if(b < l || r < a) return; if(a <= l && r <= b){ delay[k] = val; eval(l, r, k); return; } add(a, b, k*2, l, (l+r)/2, val); add(a, b, k*2+1, (l+r)/2+1, r, val); seg[k] = (seg[k*2] + seg[k*2+1]); } void add(int a, int b, llint val){ if(a > b) return; add(a, b, 1, 0, (1< G[100005]; llint a[100005]; llint parent[100005], order[100005]; llint l[100005], r[100005], l2[100005], r2[100005]; queue Q; SegTree seg(17); void bfs() { llint id = 1; order[1] = id++, parent[1] = -1; Q.push(1); llint v; while(Q.size()){ v = Q.front(); Q.pop(); l[v] = id; bool flag = false; for(int i = 0; i < G[v].size(); i++){ if(order[G[v][i]]) continue; flag = true; order[G[v][i]] = id++; parent[G[v][i]] = v; Q.push(G[v][i]); } r[v] = id-1; if(!flag) l[v] = r[v] = 0; } } int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n; llint u, v; for(int i = 1; i <= n-1; i++){ cin >> u >> v; u++, v++; G[u].push_back(v); G[v].push_back(u); } for(int i = 1; i <= n; i++) cin >> a[i]; bfs(); for(int i = 1; i <= n; i++){ for(int j = 0; j < G[i].size(); j++){ if(G[i][j] == parent[i]){ G[i].erase(G[i].begin() + j); break; } } } for(int i = 1; i <= n; i++){ if(G[i].size()){ l2[i] = n+1, r2[i] = 0; bool flag = false; for(int j = 0; j < G[i].size(); j++){ int u = G[i][j]; if(l[u] && r[u]){ l2[i] = min(l2[i], l[u]); r2[i] = max(r2[i], r[u]); flag = true; } } if(!flag) l2[i] = r2[i] = 0; } } seg.init(); for(int i = 1; i <= n; i++) seg.update(order[i], a[i]); //for(int i = 1; i <= n; i++) cout << seg.query(i, i) << " "; cout << endl; //for(int i = 1; i <= n; i++) cout << order[i] << " " << l[i] << " " << r[i] << " " << l2[i] << " " << r2[i] << endl; cin >> m; llint x; for(int q = 0; q < m; q++){ cin >> x; x++; llint sum = 0; if(l[x] > 0) sum += seg.query(l[x], r[x]); if(l2[x] > 0) sum += seg.query(l2[x], r2[x]); llint p = parent[x], pp; if(p != -1){ sum += seg.query(order[p], order[p]); if(l[p] > 0) sum += seg.query(l[p], r[p]); pp = parent[p]; if(pp != -1) sum += seg.query(order[pp], order[pp]); } else sum += seg.query(order[x], order[x]); if(l[x] > 0) seg.add(l[x], r[x], 0); if(l2[x] > 0) seg.add(l2[x], r2[x], 0); if(p != -1){ seg.add(order[p], order[p], 0); if(l[p] > 0) seg.add(l[p], r[p], 0); if(pp != -1) seg.add(order[pp], order[pp], 0); } seg.add(order[x], order[x], sum); cout << sum << "\n"; //for(int i = 1; i <= n; i++) cout << seg.query(i, i) << " "; cout << endl; } flush(cout); return 0; }